题目大意

定义S(x)为x数位和，给出N,满足的A,B组数。

解题思路

阅读题面，很容易想到这是一道数位DP能做的题。

我们先决定dp数组几个参数。可以列出dp[x][a][b][u][v]；
其中x是现在搜到的位置，ab分别表示当前的A与B，u表示当前位之前B是否等于N(B<=N)，而v表示当前位之前A是否等于B(A<=B)。

但是a,b这两个还需要再进一步简化。
所以我们可以改成dp[x][y][u][v]，其中y表示A前面位数和−B前面位数和（防负数偏移1000）。

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long dp[110][1810][2][2];
char c[910];
int l;
long long dfs(int x,int y,int u,int v)
{
    if(x>l) return y>900;
    if(~dp[x][y][u][v]) return dp[x][y][u][v];
    long long tot=0,a,b,i,j;
    if(u) a=c[x]-'0';
    else a=9;
    for(i=0;i<=a;i++)
    {
        if(v) b=i;
        else b=9;
        for(j=0;j<=b;j++)
            (tot+=dfs(x+1,y+j-i,(u && i==a),(v && j==b)))%=mod;
    }
    return dp[x][y][u][v]=tot;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%s",c+1);
    l=strlen(c+1);
    printf("%lld\n",dfs(1,900,1,1));
    return 0;
}