P2602
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
a<=b<=10^12
Solution 1：
对每一位数我们直接把数拆分，然后直接考虑因为每个数出现概率均等，所以直接可以算出出现次数
以22258为例，（） 22258=20000+2000+200+50+8
在不考虑首位时，
其中20000中（0000-9999）0，1，2 , 3....9，都出现了4000*2次
（例如0~99中共100（10x10）个数， 每个数都看作两位数（包含前导零），共100x2个单独数字出现）
2000,200,50,8以此类推
考虑首位时，考虑小于首位最大数的数字个数需要加上10000，
首位最大数个数增加2258
此时1~9已经计算出来，但0会因为前导零出现错误
最后我们减去前导零个数即可
如何计算前导零个数？
我们一100为例
前导零个数为 203-19-902-1*3
或者考虑直接算出0的个数
因为已经计算出1~9出现次数，此时我们用
19+902+1*3-Sum(1~9)就是0的个数
Solution 2:
我们直接考虑记忆化按位搜索
每次判断前面有没有前导零，这一位有没有越界（前面都是最大位时）
最后return 数字个数，从0~9按次DFS即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=15;
ll f[N][2][N][2];
int num[N];
ll dfs(int len,bool im,int sum,bool zero,int s){
ll ret=0;
if(len==0) return sum;
if(f[len][im][sum][zero]!=-1) return f[len][im][sum][zero];
for(int i=0;i<=9;i++){
if( im && i>num[len]) break;
ll ask;
bool fg,fs;
if(i==num[len] && im==1) fg=1;
else fg=0;
ask=sum+( (zero!=1 || i!=0) && i==s);
if(zero==1&&i==0) fs=1;
else fs=0;
ret+=dfs(len-1,fg,ask,fs,s);
}
f[len][im][sum][zero]=ret;
return ret;
}
ll kp(ll x,int s){
int len=0;
while(x){
num[++len]=x%10;
x/=10;
}
memset(f,-1,sizeof(f));
return dfs(len,1,0,1,s);
}
int main(){
ll a,b;
scanf("%lld%lld",&a,&b);
for(int i=0;i<=9;i++){
printf("%lld ",kp(b,i)-kp(a-1,i));
}
return 0;
}