Description

题解

• $10^{100}$的数据明示算法：数位DP
• 令状态$dp[x][d][l][s]$
• $x~$:搜到位置
• $d~$:$A$前面位数和$-B$前面位数和（防负数偏移$1000$）
• $l~$:limit,当前位之前$B$是否等于$N$,反映限制$B\leq N$
• $s~$:当前位之前$A$是否等于$B$,反映限制$A\leq B$

#include <cstdio>
#include <cstring>
const int N=110,mod=1e9+7;
using namespace std;
int n,digit[N],dp[N][N*20][2][2];
char s[N];
int dfs(int x,int d,bool l,bool s){if(!x) return d>1000;//S(A)>S(B)if(~dp[x][d][l][s]) return dp[x][d][l][s];int ret=0,lim=l?digit[x]:9;for(int i=0;i<=lim;i++)for(int j=0;j<=(s?i:9);j++)ret=(ret+dfs(x-1,d+j-i,l&(digit[x]==i),s&(i==j)))%mod;return dp[x][d][l][s]=ret;		
}int main(){memset(dp,-1,sizeof(dp));scanf("%s",s),n=strlen(s);for(int i=0;i<n;i++) digit[n-i]=s[i]-'0';printf("%d\n",dfs(n,1000,1,1));
}