题意
设 S ( x ) 为x各数位之和，如 S (123) =1+2+3=6，求有多少数对(A,B)满足S(A)>S(B) 0<=A<B<=N
N<=10^100。
看数据范围，肯定是数位DP。
首先，我们考虑简化问题：
当N=9999999……999999时答案时什么样的。
我们考虑分类讨论：
当A、B位数不同时，我们设 f [ x ] [ y ] 为共x位 ( 算前导0 )，位数和为y的数字有多少个 。设sm[x][y]为f[x][y]的后缀和。
则我们可以枚举B的和，再利用sm[x][y]O(1)求解。
当A、B位数不同时，我们枚举A在哪一位首先小于B，然后分别枚举这一位之前 与之后的 A与B的位数和。求出A、B位数相同时的数对数。
两者相加得到L[i]，表示0~999……999( 共 i 个9)的答案。
接下来，我们正式开始数位DP
我们分三种情况DP：
当B DP到从高到低第X位时
1、A在前x-1位就已经确定它一定小于此时的B
设F [ x ] [ y ]，为到当前第 x 位 时，A已经可以通过前x-1位判断出A<B 且前x-1位数位和为y的方案数。
然后枚举B在这一位填什么以及后面那些位的位数和来统计答案。
2、A前x-1位于B相同，在x拉开差距
我们枚举B与A在这一位的差值以及之后几位里B的数位和来求解
3、A与B前x为都相同且第x为小于A[i]
这里就用我们之前求出的L[i]数组乘上A[i]求解即可。
虽然思路看起来比较简单，但是边界还是很难处理的。详情请看代码。
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define N 105 8 #define M 905 9 using namespace std; 10 const int p= 1e9+7; 11 long long f[N][M]; 12 long long sm[N][M]; 13 long long L[N]; 14 char bb[N]; 15 int A[N],n; 16 long long F[2][M]; 17 int main() 18 { 19 f[0][0]=1; 20 sm[0][0]=1; 21 for(int i=1;i<=100;i++) 22 { 23 for(int j=0;j<=(i-1)*9;j++) 24 { 25 for(int k=0;k<=9;k++) 26 { 27 f[i][j+k]+=f[i-1][j]; 28 f[i][j+k]%=p; 29 } 30 } 31 } 32 for(int i=1;i<=100;i++) 33 { 34 for(int j=900;j>=0;j--) 35 { 36 sm[i][j]=sm[i][j+1]+f[i][j]; 37 sm[i][j]%=p; 38 } 39 } 40 for(int i=1;i<=100;i++) 41 { 42 for(int j=1;j<=i;j++) 43 { 44 for(int k=j*9;k>=0;k--) 45 { 46 L[i]+=(f[j][k]-f[j-1][k]+p)%p*sm[j-1][k+1]%p; 47 L[i]%=p; 48 } 49 } 50 for(int j=1;j<=i;j++) 51 { 52 long long tmp1=sm[j-1][0]; 53 for(int k=1;k<=9;k++) 54 { 55 for(int l=0;l<=(i-j)*9;l++) 56 { 57 L[i]+=(tmp1-1)*f[i-j][l]%p*sm[i-j][l+k+1]%p*(9-k+1)%p; 58 L[i]%=p; 59 L[i]+=f[i-j][l]%p*sm[i-j][l+k+1]%p*(9-k)%p; 60 L[i]%=p; 61 } 62 63 } 64 65 } 66 } 67 scanf("%s",bb+1); 68 n=strlen(bb+1); 69 long long sum=0; 70 for(int i=1;i<=n;i++) 71 { 72 A[i]=bb[i]-'0'; 73 } 74 int now=n; 75 while(A[now]==9) 76 { 77 A[now]=0; 78 now--; 79 } 80 A[now]++; 81 if(now==0) 82 { 83 for(int i=n+1;i;i--) A[i]=A[i-1]; 84 A[0]=0; 85 n=n+1; 86 } 87 long long ans=0; 88 int la=1,nw=0; 89 for(int i=1;i<=n;i++) 90 { 91 int tmp=n-i; 92 for(int j=0;j<=(i-1)*9;j++) 93 { 94 if(!F[nw][j])continue; 95 for(int k=0;k<A[i];k++) 96 { 97 for(int l=0;l<=tmp*9;l++) 98 { 99 int tmpp=sum+k+l-j+1; 100 if(tmpp<0) tmpp=0; 101 if(tmpp>=0&&tmpp<=900) 102 { 103 ans+=F[nw][j]*f[tmp][l]%p*sm[tmp+1][tmpp]%p,ans%=p; 104 } 105 } 106 } 107 } 108 for(int j=0;j<=tmp*9;j++) 109 { 110 for(int k=1;k<=A[i]-1;k++) 111 { 112 ans+=f[tmp][j]*sm[tmp][j+k+1]%p*(A[i]-k)%p; 113 ans%=p; 114 } 115 } 116 ans+=1ll*L[tmp]*(A[i])%p; 117 ans%=p; 118 nw^=1,la^=1; 119 memset(F[nw],0,sizeof(F[nw])); 120 for(int j=0;j<=(i-1)*9;j++) 121 { 122 for(int k=0;k<=9;k++) 123 { 124 F[nw][j+k]+=F[la][j]; 125 F[nw][j+k]%=p; 126 } 127 } 128 for(int k=0;k<A[i];k++) 129 { 130 F[nw][sum+k]++; 131 } 132 sum+=A[i]; 133 } 134 printf("%lld ",ans); 135 return 0; 136 } 137 /* 138 22 139 */