题解 P2602 【[ZJOI2010]数字计数】

这里介绍一种不需要数位dp的黑科技？ 当然就是只能水一水这种水题，但是别的数位dp题大家还是别用了 我们现在要统计每一个数码在\[a,b]出现了多少次 emm可以求两发前缀和再相减？ 现在问题变成了求\[1,b]内每个数码出现了多少次 比如说我们要求2出现了多少次 这里会有一个非常神奇的性质 2出现的总次数=第1位为2的数的个数+第2位为2的数个数+……第n位为2的个数 可能你会觉得会有重复，比如22222被重复统计了5次 但是我们求的不就是2的出现次数吗?22222刚好出现了5次啊…… 所以这样的统计方法是十分合理的 那么假设我们要求为第i位为k的数的个数，发现这个i把整个数分为两段，i前面的和i后面的，因此我们求出来i前面的数有多少种可能性，后边的序列有多少种可能性，两个一乘，就是第i为k的数的个数了 额以下的数码的意思就是我们把b的前i位/后i位写下来，形成的那个十进制数字 那么假如k比b的第i位小的话，k后边的数可以从00……-99……随便取，因为这一位已经小了，所以后边如何取都不会影响大小，所以后边的方案数是$10^{i-1}$ 现在的问题就是如何取前面的数，发现只需要前面的数码<=b的数码就可以了，因此一共有$b/10^{i}+1$种方案，加的1是因为前导0也属于一个合法的方案 如果k比b这一位的大的话后边的也是可以随便取的，因为前面已经大了，所以后边如何取也不会影响大小，因此还是有$10^{i-1}$的方案数，但是前面的数吗不可以取等，因此方案数就是$b/10^{i}-1+1=b/10^{i}$同理+1也是因为前导0也属于一个合法的方案 现在是最为辣手的情况了，如果k和b的这一位相等，那么首先我们按大于的时候处理当然是满足条件的，但是还有一种情况，如果前面的东西取了等，此时我们后边的数字如果小于b后边的数码当然是可以的，为此我们先按大于的公式计算一波，最后在加上b后i-1位的数码，这个可能需要递推 最后特判一发最高位不可以是0就行了~ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=15;typedef long long ll; ll lim[N];ll suf[N];ll mi[N];ll pre[N];ll res[2][N];int n;ll a;ll b; inline void solve(ll x,ll* res) { for(n=1;x;n++,x/=10LL){lim[n]=x%10LL;}n--;suf[n+1]=0;pre[0]=1; for(int i=1;i<=n;i++){pre[i]=suf[i]=0;} for(int i=1;i<=n;i++){pre[i]=pre[i-1]+lim[i]*mi[i-1];}//这里直接递推了前i位和后i位的数码 for(int i=n;i>=1;i--){suf[i]=suf[i+1]*10LL+lim[i];} for(int i=1;i<=n;i++) { if(i!=n)//判一下0 { if(lim[i]!=0){res[0]+=mi[i-1]*suf[i+1];} else {res[0]+=mi[i-1]*(suf[i+1]-1)+pre[i-1];} } for(int j=1;j<=9;j++)//然后分3种情况讨论就行啦 { if(j>=lim[i]){res[j]+=mi[i-1]*suf[i+1];}//case1 else {res[j]+=mi[i-1]*(suf[i+1]+1LL);}//case2 if(j==lim[i]){res[j]+=pre[i-1];}//case3 } } } int main() { scanf("%lld%lld",&a,&b);mi[0]=1; for(int i=1;i<=13;i++){mi[i]=mi[i-1]*10LL;}//这里预处理下10的幂次 solve(b,res[0]);solve(a-1,res[1]);//然后solve两发就可以解决啦~ for(int i=0;i<=9;i++){printf("%lld ",res[0][i]-res[1][i]);}return 0;//拜拜程序~ } ```