题目
UVa 1640 The Counting Problem
题解
一开始知道是数位DP我是拒绝的。。因为本人数位DP弱成渣。而且紫书上给的啥鬼畜的分块计算方法。。完全不懂，只有按照自己的理解写一个数位DP，写的时候也是缝缝补补剪剪裁裁，漏了加多了减，东拼西凑出了答案。
对于刘汝佳的分块我觉得分的太小了，比如说234，要分就分成0~199,200~229,230~234,这样的话，0~199后两位相当于是两个0~99，也方便计算，可以知道，如果后i位能随便选的话，每个数字会出现 10i?i10=10i?1?i 次，那采用如下方式按块算。
比如刚拿到234，从第3位（从右往左数）开始，设该位上界为lim（这里为2）,那么对于 [0,lim?1] 里面的数字，后两位一定分别对应了一个可以有3-1位随便选的块，这一点 [0,lim?1] 里面的数字是一样的，并且如果这个数字为i，那么由于后两位可以随便选，所以i在这一位上会出现 103?1 次，而对于lim来说，这位上会出现 x%103?1+1 个lim，加1是因为是从0开始的，然后递归下去算就行了（其实好像可以不递归）。（上面用3-1是为了明确式子与当前位置的关系）
写到一半发现，在第pos位枚举 i(0<=i<lim) 时，如果i为0，会有前导0的影响，因为我默认后面的数有pos-1位，其实可能没有那么多位，不足的位上的0也被算进去了，卡了半天差点放弃了，不过可以发现，对于上面的例子，多算的0仅出现计算0~99时，而多算的前导0的数量是有规律的，比如对于10~99的90个数多算1个，0~9十个数多算2个，那对于 [0,10i?1] 这个区间内，前导0的数量就会有 ∑i?1k=19?10i?k?k+10?i 个，注意最后有0~9这10个数。算完了减了就行了。
代码
代码写的丑。。
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int a,b,sum[10],sum0[10],c10[10];
int cnt1[10],cnt2[10];
//sum[i]表示最后i位随意取时出现某个数字的次数
//c10[i]=10^iinline void init_sum()
{c10[0]=1;for(int i=1;i<=9;++i) c10[i]=c10[i-1]*10;for(int i=1;i<=10;++i) sum[i]=c10[i]*i/10;
}int ret;
//获取a的位数
inline int getlen(int a){
for(ret=0;a;a/=10) ++ret;return ret;}
//获取a从右往左第pos位上的数
inline int getnum(int a,int pos){
return a/c10[pos-1]%10;}//对于多统计的前导0，算完之后统一减回去
void dfs(int pos,const int &x,int *cnt)
{int lim=getnum(x,pos);if(pos==1){for(int i=0;i<=lim;++i) ++cnt[i];return ;}for(int i=0;i<lim;++i){cnt[i]+=c10[pos-1];for(int j=0;j<=9;++j) cnt[j]+=sum[pos-1];}cnt[lim]+=x%c10[pos-1]+1;if(pos==getlen(x)) {for(int k=1;k<=pos-2;++k)cnt[0]-=9*c10[pos-1-k]*k;cnt[0]-=10*(pos-1);}dfs(pos-1,x,cnt);
}inline void solve()
{memset(cnt1,0,sizeof(cnt1));memset(cnt2,0,sizeof(cnt2));for(int i=0;i<=9;++i)if(a>b) swap(a,b);dfs(getlen(a),a-1,cnt1);dfs(getlen(b),b,cnt2);for(int i=0;i<9;++i) printf("%d ",cnt2[i]-cnt1[i]);printf("%d\n",cnt2[9]-cnt1[9]);
}int main()
{init_sum();while(scanf("%d%d",&a,&b)==2){if(!a&&!b) break; solve();}return 0;
}