P2602 数字计数

统计题

数字统计可以用一些特殊的方法来求

两位数的时候

latex

例如：10~99 中 0，1，2，3，4，5，6，7，8，9 分别出现的次数

可以先看最高位有 $1$~$9$，$9$ 种选择，再看各位，$0$~$9$，$0$ 种选择，也就是说，只看十位 $1$x 有 $10$ 个 $1$，看个位 x$1$ 有 $9$ 个$1$。

$1$ 出现次数可以表达成 $1\times9+1\times10=19$ 和 $2$，$3$，$4$，$5$，$6$，$7$，$8$，$9$ 一样，但 $0$ 不一样，因为不能在最高位，所以出现的次数为 $1\times9=9$ 次

latex

答案为：9，19，19，19，19，19，19，19，19，19

三位数的时候

latex

例如：100~999 中 0，1，2，3，4，5，6，7，8，9 分别出现的次数

可以先看最高位有 $1$~$9$,$9$ 种选择，再看十位，$0$~$9$，$10$ 种选择，再看个位，$0$~$9$，$10$ 种选择，也就是说：

只看百位 $1$xx 有 $100$ 个 $1$，只看十位 x$1$x 有 $9\times10$ 个 $1$，只看个位 xx$1$ 有 $9\times10$ 个一。

$1$ 出现的次数可以表达成 $100+9\times10+9\times10=280$

$0$ 呢？$9\times10+9\times10=180$

四位数的时候（重点）

latex

例如：1000~9999 中 0，1，2，3，4，5，6，7，8，9 分别出现的次数

可以先看最高位有 $1$~$9$,$9$ 种选择，再看百位，$0$~$9$，$10$ 种选择，再看十位，$0$~$9$，$10$ 种选择，再看个位，$0$~$9$，$10$种选择，也就是说，

只看千位 $1$xxx 有 $1000$ 个 $1$，只看百位 x$1$xx 有 $9\times10\times10$ 个 $1$，只看十位 xx$1$x 有 $9\times10\times10$ 个 $1$ ，只看个位 xxx$1$ 有 $9\times10\times10$ 个一。

$1$ 出现的次数可以表达成 $1000+9\times10\times10+9\times10*\times10+9\times10\times10=3700$

$0$ 呢？$9\times10\times10+9*10\times10+9\times10\times10=2700$

小结

是 $C^m_n$？但是：

latex

例如：673~9283 中 0，1，2，3，4，5，6，7，8，9 分别出现的次数

进阶

latex

通过仔细地观察，可以发现，可以将这些数拆分。
1673->1000+600+70+3
  
经过细致的观察，发现可以寻找一个中间量：2000，先求出 2000~9283 中分别的数，再求出 1673~2000 中各数的出现次数。

还要拆分： 9283->9000+200+80+3
变成了 2000~9283->2000~9000+9001~9283，9201->9280，9281->9283

1673->2000 就先对容易多了
不断拆分即可

最后

碰见位数不同的就可以 $0$ 补位！！！

传送门

代码

cpp

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
long long a,b,w_w[20],f[20],x[20],y[20];
void ji(long long x,long long *xy){
    long long num[20]={0};
    int len=0;
    while(x){
        num[++len]=x%10;
        x=x/10;
    } 
    for(int i=len;i>=1;i--){
        for(int j=0;j<=9;j++)
        xy[j]+=f[i-1]*num[i];
        for(int j=0;j<num[i];j++)
        xy[j]+=w_w[i-1];
        long long num2=0;
        for(int j=i-1;j>=1;j--){
            num2=num2*10+num[j];
        }
        xy[num[i]]+=num2+1;
        xy[0]-=w_w[i-1];
    } 
}
int main(){
    cin>>a>>b;
    w_w[0]=1;
    for(int i=1;i<=15;i++){
        f[i]=f[i-1]*10+w_w[i-1];
        w_w[i]=10*w_w[i-1];
    }
    ji(a-1,x);ji(b,y);
    for(int i=0;i<=9;i++)cout<<y[i]-x[i]<<" ";
    return 0;
}