https://www.luogu.org/problemnew/show/P2602
第二道数位dp，因为“数位dp都是模板题”（误），所以是从第一道的基础上面改的。
核心思想就是分类讨论，分不同情况讨论对答案的贡献。
最最重要的是，该数位取与当前位相等的时候，贡献的个数是受这个数位影响的所有数（这个写法里包括它本身），那么就用x减去与x前缀相同的“整数”再+1就可以算出来了。
其他的数位dp……好像就不太会写了，再研究一下。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[][][];
ll pow10[]; ll sum(int i,int j1,int j2,int k){
if(j1<)
j1=;
if(j2>)
j2=;
ll res=;
for(int j=j1;j<=j2;j++){
res+=dp[i][j][k];
}
return res;
} void init(){
pow10[]=;
for(int i=;i<=;i++){
pow10[i]=pow10[i-]*;
} for(int j=;j<=;j++)
dp[][j][j]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
dp[i][j][k]=sum(i-,,,k);
if(j==k){
dp[i][j][k]+=pow10[i-];
}
}
}
} /*for(int j=1;j<=2;j++){
dp[9][j]=sum(8,0,j-2)+sum(8,j+2,9);
}*/ /*for(int i=1;i<=13;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++)
printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]);
}
printf("\n");
}*/
} ll A,B;
int digit[]; int w; ll count(ll x){
//cout<<"x="<<x<<endl;
if(x<)
return ;
if(x==){
if(w==)
return ;
else
return ;
}
//否则岂不是0位数？
ll k=,cx=x;
digit[k++]=;
//占位用的
while(cx){
digit[k++]=cx%;
cx/=;
}
k--;
digit[k+]=;
//也是占位 ll res=;
for(int i=k;i>=;i--){
//printf("i=%d res=%d\n",i,res);
if(i==k){
//最高位取0
for(int ii=i-;ii>=;ii--){
res+=sum(ii,,,w);
//printf("you want=%d\n",res);
}
if(w==)
res+=;//0
//其实不用特判啊
for(int j=;j<digit[i];j++){
//最高位比digit小且不为0 if(i->=){
if(j==w)
res+=pow10[i-];
res+=sum(i-,,,w);
}
else{
if(j==w)
res+=;
}
}
//最高位就取相等，问题留给下一次循环
//取相等怎么会是满的呢？
if(digit[i]==w)
res+=(x-x/pow10[i-]*pow10[i-]+);
}
else{
//前面的位都相等，非最高位的情况
for(int j=;j<digit[i];j++){
if(i->=){
if(j==w)
res+=pow10[i-];
res+=sum(i-,,,w);
}
else{
if(j==w)
res+=;
}
}
if(digit[i]==w)
res+=(x-x/pow10[i-]*pow10[i-]+);
}
} //一直相等的情况在上面自动处理了，不用另外处理
/*for(int i=1;i<=k;i++){
if(digit[i]==w){
res++;
}
}*/
//printf("res=%d\n",res);
return res;
} int main(){
init();
while(~scanf("%lld%lld",&A,&B)){
for(w=;w<=;w++)
printf("%lld%c",count(B)-count(A-)," \n"[w==]);
}
}
后来学会了搜索写法。