数位dp总结
分类：
一类是单纯地统计满足条件的个数，一类是要求类似于数位和、平方和一类的。其实第二类是基于第一位的基础上的，只是要开一个结构体去存有关要维护的信息，例如：恨7不成妻(数位DP求平方和)。
解题套路：
找到限制条件->dfs传参->考虑将哪些限制条件放入dp
虽然基础的数位dp看起来很简单，打起来也很简单，但是还是有很多细节需要注意
细节：
1.取模的时候一定要记得+mod %mod！！ 否则很容易答案为负数！！
2.有多个限制条件时，要考虑将哪些放入dp的维度中，否则答案会不一样（不知道放哪些可以试一试）
3.dp的初始值一定要为-1，因为0状态也可能是被更新过的，也应该返回（否则在某些题里面会超时）。
第一类dp的几道简单题：
数字计数
#include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int N = 15; ll f[N][2][N][2]; int num[N]; //num来存这个数每个位子上的数码 /* 记忆化搜索。 len是当前为从高到低第几位。issmall表示当前位是否和num[len]相等，0是相等，1是不相等。 sum表示当前数字出现的次数。zero表示之前是否是前导0。d是当前在算的数码。 */ ll dfs(int len, bool issmall, int sum, bool zero, int d) { ll ret = 0; if (len == 0) return sum; //边界条件 if (f[len][issmall][sum][zero] != -1) return f[len][issmall][sum][zero]; //记忆化 一般用-1作为判断条件！！！ for (int i = 0; i < 10; i ++){ if (!issmall && i > num[len]) break;//剪枝很重要！！ /* 由于我们是从高位到低位枚举的，所以如果之前一位的数码和最大数的数码相同，这一位就只能枚举到num[len]； 否则如果之前一位比最大数的数码小，那这一位就可以从0~9枚举了。 */ ret += dfs(len-1, issmall || (i<num[len]), sum+((!zero || i) && (i==d)), zero && (i == 0), d); /* 继续搜索，数位减一，issmall的更新要看之前有没有相等，且这一位有没有相等； sum的更新要看之前是否为前导0或者这一位不是0； zero的更新就看之前是否为前导0且这一位继续为0； d继续传进去。 */ } f[len][issmall][sum][zero] = ret; //记忆化，把搜到的都记下来 return ret; } ll solve(ll x, int d) { int len = 0; while (x){ num[++ len] = x%10; x /= 10; } //数字转数位 memset(f, -1, sizeof f); //初始化 return dfs(len, 0, 0, 1, d); //开始在第len位上，最高位只能枚举到num[len]所以issmall是0，sum=0，有前导0。 } int main() { ll a, b; //注意都要开long long scanf("%lld%lld", &a, &b); for (int i = 0; i < 10; i ++) printf("%lld%c", solve(b, i)-solve(a-1, i), i == 9 ? ' ' : ' '); return 0; }
windy数
#include<bits/stdc++.h> using namespace std; int f[15][15],a[15]; int dfs(int now,int pre,int ling,int lim) { if(now==0) return 1; if(!lim&&!ling&&f[now][pre]!=-1) return f[now][pre]; int jie=9,ret=0; if(lim) jie=a[now]; for(int i=0;i<=jie;i++) { if(abs(i-pre)<2) continue; int nxlin=0,nxlim=0,p=i; if(i==0&&ling) nxlin=1,p=-22; if(lim&&i==jie) nxlim=1; ret+=dfs(now-1,p,nxlin,nxlim); } if(!ling&&!lim) f[now][pre]=ret; return ret; } int work(int s) { memset(a,0,sizeof(a)); int len=0; while(s) { a[++len]=s%10; s/=10; } //printf("la %d %d %d ",a[1],a[2],len); memset(f,-1,sizeof(f)); return dfs(len,-22,1,1); } int main() { int l,r; scanf("%d%d",&l,&r);// printf("%d ",work(r)-work(l-1)); } /* 1 10 ans 9 */
萌数
题意：求含回文串的个数
思路：补集转换->求出不含回文串的数->只需记录前面和前前面的数是否一样（一个回文串一定是由回文中心扩展而来）
难点：范围是10^1000怎么计算l-1是什么数->求0~l范围内的，然后check一下l是不是萌数即可
初始时pre和pp的初始值应该是-1，但如果有前导0，那么参数也要赋成-1
#include<bits/stdc++.h> using namespace std; #define N 1005 #define ll long long #define mod 1000000007 char l[N],r[N]; int wei,num[N]; ll dp[N][12][12]; ll dfs(int pos,int pp,int pre,int lim,bool zero) { if(pos==0) return (!zero); //主要判定的条件：没有前导0 没有压上界 前面两位都填了数 if(!lim&&dp[pos][pp][pre]!=-1&&pp!=-1&&pre!=-1&&!zero) return dp[pos][pp][pre]; int up=lim?num[wei-pos+1]:9;//这里一定要记得倒过来 ll rt=0; for(int i=0;i<=up;i++){ if(i!=pp&&i!=pre&&!zero)//跳过会形成回文的 rt=(rt+dfs(pos-1,pre,i,lim&&i==up,0))%mod; else if(zero)//如果有前导0的就都可以选 //注意前一位不能单纯是现在这一位 如果还有前导0 就应该是-1！！！ rt=(rt+dfs(pos-1, -1 , (i==0)?-1:i , lim&&i==up , i==0 ))%mod; } if(!lim&&!zero&&pre!=-1&&pp!=-1) return dp[pos][pp][pre]=rt; return rt; } ll solve(char s[]) { wei=strlen(s); memset(dp,-1,sizeof(dp)); ll tot=0; for(int i=0;i<wei;i++) num[i+1]=s[i]-'0',tot=(tot*10+s[i]-'0')%mod; //tot++; //printf("%d %d ",tot,dfs(wei,-1,-1,1,1)); return (tot-dfs(wei,-1,-1,1,1)+mod)%mod;//+mod %mod } int main() { scanf("%s%s",l,r); //scanf("%s",l); //solve(l); ll ans1=solve(r),ans2=solve(l); int lenl=strlen(l); char pp=l[0],pre=l[1]; for(int i=2;i<lenl;i++){ if(l[i]==pre||l[i]==pp){ ans2--; break; } pp=pre; pre=l[i]; } printf("%lld ",(ans1-ans2+mod)%mod);//一定要记得防止出现负数+mod %mod return 0; } /* 1 100 100 1000 ans 253 10716 27142 */
第二类dp：
最后总结：
有时候要加前导0的限制，有时候其实也不需要，主要看r-(l-1)的计算能不能把与前导0有关的数抵消。然后注意一下要不要特殊处理0这类易错的数。最重要的是+mod %mod，经常忘啊！！