ZJOI2010 数字统计
上题题意为求[l,r]区间中每个数字（0~9）出现的次数
一般的做法为将区间当成[0,r]-[0,l-1],然后进行数位DP
但事实上将区间当成[0,r]-[0,l-1]后可以有另一种方法求出[0,x]中k出现的次数
具体做法：
我们对于每一位,求出k在这一位的数中有多少小于等于x，累加即可。（注意0不能前导，要分开处理）
#define ll long long
inline ll query(ll x,int k){//询问[0,x]的数字中k出现的次数
if(x<)return ;
ll sum=,a=,i=,s=,x1;
while(x/){//枚举k出现在每一位
i=x%,x/=;//i表示k出现的这一位在原数中是什么,x表示原数中i之前的数字
x1=x;
if(!k) x1--;//因为不能有前导零，所以0要分开
if(i>k)sum+=s*(x1+);//3种情况分类讨论
else if(i==k)sum+=s*x1+a;
else sum+=s*x1;
a+=i*s,s*=;//a表示原数中i之后的数字+1
}
if(!k)return sum+;//为k为0就无法做第一位
else{//考虑x做第一位的情况
if(x>k)return sum+s;
if(x==k)return sum+a;
return sum;
}
}