数位dp

思想

一般来说，题目是要求在区间\([l,r]\)中符合某一种条件的数的个数

我们用前缀和的思想考虑，分别求出\([1,r]\)和\([1,l-1]\)中数的个数相减即为所求

这里采用记忆化搜索的方式实现

(资料图)

模板

#include#include#include#define int long long//这是因为数位问题的结果一般比较大，直接使用longlongint dp[N][N][……];//DP数组，第一维代表数的长度，其他维由具体问题决定vectornums;//分解出的每一位数字int len;int dfs(int pos, status, int limit, int zero){    if(pos>len) return //根据status返回结果，不是0就是1;    if(!zero && !limit && dp[pos][status]!=-1) return dp[pos][status];    int last = limit ? nums[len-pos-1] : 9;    int ans = 0;    for(int i=0;i<=last;++i){        ans += dfs(pos-1,newStatus,newLead,limit&&i==last);    }    if(!zero&&!limit) dp[pos][status] = ans;        return ans;}int calc(int n){    if(!n) return //视具体情况    nums.clear();    memset(dp,-1,sizeof dp);    while(n) nums.push_back(n%10),n/=10;    len = nums.size();    return dfs(0,……)}

说明

\(zero\)表示是否有前导零，当考虑的数是否需要记录和数位中0有关的数时需要前导零标记,无关时可以没有\(zero\)标记

举个例子：假如我们要从 \([0,1000]\) 找任意相邻两数相等的数

显然 \(111,222,888\) 等等是符合题意的数

但是我们发现右端点 \(1000\) 是四位数

因此我们搜索的起点是 \(0000\) ，而三位数的记录都是 \(0111,0222,0888\) 等等

而这种情况下如果我们直接找相邻位相等则 \(0000\) 符合题意而 \(0111,0222,0888\) 都不符合题意了

所以我们要加一个前导0标记

例题1 Windy数

#include#include#includeusing namespace std;int dp[12][12],len;vectornums;int dfs(int pos,int pre, int limit,int zero){if(pos>len-1) return 1;if(!limit&&!zero&&dp[pos][pre]!=-1) return dp[pos][pre];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){if(ipre-2&&!zero) continue;ans += dfs(pos+1,i,limit&&(i==res),!i&&zero);}if(!limit&&!zero) dp[pos][pre] = ans;return ans;}int calc(int n){if(n==0) return 1;memset(dp,-1,sizeof dp);nums.clear();while(n) nums.push_back(n%10),n/=10;len = nums.size();return dfs(0,-2,1,1);}int main(){int a,b;cin>>a>>b;cout<

例题2 手机号码

#include#include#include#define int long longusing namespace std;int f[15][15][15][2][2][2],len; //[位置][前一位][前两位][是否有8][是否有4][是否连续3个] vectornums;int dfs(int pos,bool limit,int pre1,int pre2,bool _8,bool _4,bool _3){if(_8&&_4) return 0;if(pos>len-1) return _3;if(!limit&&f[pos][pre1][pre2][_8][_4][_3]!=-1) return f[pos][pre1][pre2][_8][_4][_3];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){ans+=dfs(pos+1,limit&&(i==res),i,pre1,_8||i==8,_4||i==4,_3||(i==pre1&&pre1==pre2));}if(!limit) f[pos][pre1][pre2][_8][_4][_3] = ans;return ans;}int calc(int n){memset(f,-1,sizeof f);nums.clear();while(n){nums.push_back(n%10);n/=10;}if(nums.size()!=11) return 0;int res = 0;len = nums.size();for(int i=1;i<=nums[len-1];i++){res+=dfs(1,i==nums[len-1],i,0,i==8,i==4,0);}return res;}signed main(){int l,r;cin>>l>>r;cout<

例题3 圆数

#include#include#include#includeusing namespace std;int f[35][35][35],len;vectornums;int dfs(int pos,int sum1,int sum0,int limit,int zero){if(pos>len-1) return sum0>=sum1;if(!limit&&!zero&&f[pos][sum1][sum0]!=-1) return f[pos][sum1][sum0];int ans = 0;int res = limit?nums[len-pos-1]:1;for(int i=0;i<=res;i++){if(zero&&(!i)) ans+=dfs(pos+1,0,0,limit&&i==res,1);else{ans+=dfs(pos+1,sum1+(i==1),sum0+(i==0),limit&&i==res,0); }}if(!limit&&!zero) f[pos][sum1][sum0] = ans;return ans;}int calc(int n){if(!n) return 1;nums.clear();memset(f,-1,sizeof f);while(n) nums.push_back(n%2),n/=2;len = nums.size();int res = 0;res += dfs(0,0,0,1,1);return res;}int main(){int l,r;cin>>l>>r;cout<

例题4 同类分布

#include#include#include#define int long longusing namespace std;int f[20][200][200],len,mod;vectornums;int dfs(int pos,int sum,int st,int limit){if(pos>len-1) return sum==mod&&st==0;if(!limit&&f[pos][sum][st]!=-1) return f[pos][sum][st];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){ans+=dfs(pos+1,sum+i,(10*st+i)%mod,limit&&(i==res));}if(!limit) f[pos][sum][st] = ans;return ans;}int calc(int n){if(!n) return 0;nums.clear();int res = 0;while(n) nums.push_back(n%10),n/=10;len = nums.size();for(mod=1;mod<=9*len;mod++){memset(f,-1,sizeof f);res+=dfs(0,0,0,1);}return res;}signed main(){int a,b;cin>>a>>b;cout<