对于数位dp的题目，我学习的是y总的模板，也就是说把所有数先用拆位后考虑从头开始考虑，形成一个树的形状
左分支为填0-ai-1的情况，这列情况一般可以通过数学公式一次性求出，之后右分支就填当前数，这样向下延申，在最后特判右分支的情况，也就是一个数
对于数位dp，一般存储两个量，一个是个数，一个是last，用来保存前缀信息。这些都是基本思路
其他的需要根据题目来分析：
#include<iostream> #include<vector> using namespace std; const int N=35; int f[N][N]; int x,y,k,b; void init(){ int i,j; for(i=0;i<N;i++){ for(j=0;j<=i;j++){ if(!j) f[i][j]=1; else{ f[i][j]=f[i-1][j]+f[i-1][j-1]; } } } } int dp(int n){ if(!n) return 0; vector<int> num; while(n){ num.push_back(n%b); n/=b; } int res=0; int last=0; int i; for(i=num.size()-1;i>=0;i--){ int x=num[i]; if(x){ res+=f[i][k-last]; if(x>1){ if(k-last>0) res+=f[i][k-last-1]; break; } else{ last++; if(last>k) break; } } if(!i&&last==k) res++; } return res; } int main(){ init(); cin>>x>>y>>k>>b; cout<<dp(y)-dp(x-1)<<endl; }
原文：https://www.cnblogs.com/ctyakwf/p/12644184.html
