最近在写DP，今天把最近写的都放上来好了,,,
题意：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
首先询问的是一个区间，显然是要分别求出1 ~ r ,1 ~ l的答案，然后相减得到最终答案
首先我们观察到，产生答案的区间是连续的，且可以被拆分，
也就是说0 ~ 987的贡献= 0 ~ 900 + 901 ~ 987的贡献，
同理，把位拆开也是等价的，所以我们可以单独计算每个位的贡献
这样讲可能有点不太清晰，举个例子吧
3872
我们先把它按数拆开来算：分为0 ~ 999 + 1000 ~ 3872
然后再把1000 ~ 3872的部分按位拆开来算
设f[i][j]为到了第i位j出现的次数（i=2 00 ~ 99）,注意允许前导0的存在，只是必须是共i位
对于一个数n，若有t位，那么前面那部分是t-1位的，后面则是计算t位的（因为前面t-1位没有限制）
因此我们先加上t-1位的数字出现次数，
首先当i=1时，显然f[i][j]=1,
当i变为2时，我们可以脑补一下，2位可以拆分为1位+1位，而前面的1位有10种可能，因此后面的1位会出现10次，
而前面的一位也因此使得每种数字要+10，
当i变为3时，我们可以再次脑补，3位可以拆分为1位+2位，前面的一位还是有10种可能，因此后面的2位会出现10次，
而前面的一位也因此使得每种数字要+100
……
于是观察可得
f[i][j] = f[i-1][j] * 10 + 10^(i-1);
因此第一部分：
ans[j] += f[cnt-1][j];
为什么只要加这个呢？
因为这个是从0开始的啊！
比如当cnt-1==3时，
f[cnt-1][j]记录的就是000 ~ 999的出现次数，
显然包括了1位2位3位的，
但是这样会有前导0，怎么办呢？
把数字列出来稍微观察一下即可得知：
对于任意一个数而言，其前导0个数为总位数减去有效位数
也就是说0位的数有3个前导0，如000
1位的数有2个前导0，如002
2位的数有1个前导0，如078
3位的数没有前导0，如364
因此我们只需要分别减去这些位数的前导0即可，
每个位数要减掉的前导0为：对应的前导0个数 * 有多少个数
比如1位的数有2个前导0，那么这部分的前导0个数为：2 * 9
而0位的数的前导0个数为：3 * 1
这样可以观察到在某种情况下后面要乘的那个数是不好计算的，
所以我们通过前缀和来计算它，
第0位时，一共有1个数，
第1位时，一共有10个数（包括0位的），
感觉有点说不清了。。。。
就是说
000 ----> 1个数
001
。
。
009 ---->10个数
010
011
。
。
099 ---->100个数
而我们要做的就是要获取单独的每一段（被换行隔开的）有多少个数
那么很显然
010 ~ 099的数的个数就是100 - 10，
所以我们在计算的时候记录第一个sum表示在当前位之前的前缀和，t表示包括当前位的数的总个数，
比如计算到010 ~ 099这一段的时候，sum = 10,t=100,个数为t - sum = 90个
于是现在我们就可以开始计算第2部分了：
1000 ~ 3872
对于这部分，我们按位处理，
方法不太好说，还是用例子说明吧，
从高位开始算，
最高位是3，
那么很显然1000~2999这部分是满的（即都可以取到），因此我们计算的方法就是
用第一位 + 后3位，
对于1000 ~ 1999来说，第一位的1出现了1000次，我们加上，
那后面的部分对应的次数就是000 ~ 999 的次数对不对！也就是f[3][j]了
2000 ~ 2999同理即可，
因此我们要加的f[3][j]的个数就是2
那么我们现在只需要处理3000~3872了，
同样按位处理，
第一位的3出现了873次（还有000的一次），我们加上，
然后就是要计算872的贡献了，
那这部分怎么求呢？
和计算3872是一样的啊（是不是很像递归），
还是先算000~799
但是也不完全一样，有一点不同，
因为此时已经不再是第一位了，所以前导0是允许存在的，
所以这个时候，在处理第一位的时候就需要考虑
000 ~ 099了，
而在第一位时只需从100 ~ 199开始考虑，
多加上对应的次数即可。
貌似有点啰嗦了。。。。
下面是代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define LL long long 5 #define AC 15 6 LL l,r,cnt,tot; 7 LL ansl[AC],ansr[AC],f[AC][AC];//f[i][j] : 到了第i位(i = 2,00 ~ 99)，j出现的次数 8 int numl[AC],numr[AC]; 9 /*由于枚举位数，所以不考虑前导零， 10 因此就可以直接递推次数了? 11 次数必须严格保证是i位的，就是说就算是000也要凑够i位 12 */ 13 void pre() 14 { 15 scanf("%lld%lld ",&l,&r); 16 l -= 1;//因为我计算的是r - l的，但是l要包括进来，，，，懒得改了，就在这里减一下吧 17 LL tmp=l; 18 while(tmp) 19 { 20 numl[++cnt]=tmp % 10; 21 tmp /= 10; 22 } 23 tmp=r; 24 while(tmp) 25 { 26 numr[++tot]=tmp % 10; 27 tmp /= 10; 28 } 29 for(R i=0;i<=9;i++) f[1][i]=1; 30 tmp=10; 31 for(R i=2;i<=tot;i++)//枚举位数 32 { 33 for(R j=0;j<=9;j++) 34 f[i][j] = f[i-1][j] * 10 + tmp;//因为新加入的第一位有10种，所以原来的位数要乘10 35 tmp *= 10; 36 } 37 /*for(R i=1;i<=tot;i++) 38 { 39 for(R j=0;j<=9;j++) 40 printf("%lld ",f[i][j]); 41 printf(" "); 42 }*/ 43 } 44 45 void work1() 46 { 47 LL tmp=1; 48 for(R i=1;i<cnt;i++) tmp *= 10; 49 for(R j=0;j<=9;j++) ansl[j] += f[cnt-1][j];//就是这里会产生前导零吧,不过是整段的，可以稍作分析解决 50 LL t=1,sum=0;//现在是t个数码 51 for(R i=0;i<cnt;i++)//枚举位数（预先加的只有cnt-1位的ans,因为只有这部分是完整的) 52 { 53 ansl[0] -= (t - sum) * (cnt - 1 - i);//i位被占用，剩下的都是0 54 sum += t - sum;//累加上当前的数码个数 55 t *= 10;//10 ^ i个数码 56 } 57 for(R i=cnt; i ;i--) 58 { 59 int b = (i == cnt);//这里和下面都要特判第一位(因为有0取与不取的问题，即开头是否可以为0) 60 for(R j=b;j<numl[i];j++)//先统计当前位的 61 ansl[j] += tmp; 62 l -= numl[i] * tmp; 63 ansl[numl[i]] += l + 1; 64 if(i == cnt)//error!!!必须大于等于1才行 65 { 66 for(R j=0;j<=9;j++) 67 ansl[j] += f[i-1][j] * (numl[i] - 1);//这里只能批量加上前几个的，后面的是不规则的，要到后面处理 68 } 69 else 70 { 71 for(R j=0;j<=9;j++) 72 ansl[j] += f[i-1][j] * numl[i];//因为之后可以算0的了，所以就不要-1了 73 } 74 tmp /= 10; 75 } 76 } 77 78 void work2() 79 { 80 LL tmp=1; 81 for(R i=1;i<tot;i++) tmp *= 10; 82 for(R j=0;j<=9;j++) ansr[j] += f[tot-1][j];//就是这里会产生前导零吧,不过是整段的，可以稍作分析解决 83 LL t=1,sum=0;//现在是t个数码 84 for(R i=0;i<tot;i++)//枚举位数（预先加的只有tot-1位的ans,因为只有这部分是完整的) 85 { 86 ansr[0] -= (t - sum) * (tot - 1 - i);//i位被占用，剩下的都是0 87 sum += t - sum;//累加上当前的数码个数 88 t *= 10;//10 ^ i个数码 89 } 90 for(R i=tot; i ;i--) 91 { 92 int b = (i == tot);//因为只有第一位的0不合法，所以后面是可以统计到0的 93 for(R j=b;j<numr[i];j++)//先统计当前位的 94 ansr[j] += tmp; 95 r -= numr[i] * tmp;//这里本意就是要获取低于当前位的数码，因此前面减掉了的要在r里面也减掉，不然获取不出来 96 //ansr[numr[i]] += r - numr[i] * tmp + 1; 97 ansr[numr[i]] += r + 1;//因为前面已经减过了，所以这里就不要减了 98 if(i == tot)//error!!!必须大于等于1才行 99 { 100 for(R j=0;j<=9;j++) 101 ansr[j] += f[i-1][j] * (numr[i] - 1);//这里只能批量加上前几个的，后面的是不规则的，要到后面处理 102 } 103 else 104 { 105 for(R j=0;j<=9;j++) 106 ansr[j] += f[i-1][j] * numr[i];//因为之后可以算0的了，所以就不要-1了 107 } 108 tmp /= 10; 109 } 110 /*for(int i=0;i<=9;i++) printf("%lld ",ansl[i]); 111 cout << endl; 112 for(int i=0;i<=9;i++) printf("%lld ",ansr[i]); 113 cout << endl;*/ 114 for(R i=0;i<9;i++) printf("%lld ",ansr[i] - ansl[i]); 115 printf("%lld ",ansr[9] - ansl[9]); 116 } 117 118 int main() 119 { 120 // freopen("in.in","r",stdin); 121 pre(); 122 work1(); 123 work2(); 124 // fclose(stdin); 125 return 0; 126 }