【数位DP-技巧】长度为N的数串每M个和都为质数
Description
经过不懈的努力,你在后山挖出了一个宝箱,旁边还有一张纸条,上面写着两个数字还有一段话:“我是九头龙晗源,想要我的资源吗?如果想要的话,那就到oj.cqupt.edu.cn.cqu.pt去找吧,我全部都放在那里。密码是满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。N和M我写在纸上了。”
Input
每个输入包含一个测试用例。 每个测试用例包括两个整数N(1<=N<=12)和M(1<=M<=4)。
Output
输出一个整数,表示密码,即满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。 这N位数字每一位可以是0~9,数字串可以有前导0。
Sample Input
2 2
Sample Output
37
HINT
当M>N时,密码为0
无脑滚表虽然过了,但和MZJJ学到了很多数位dp的技巧。
比如如何取位,如何快速加和一个3位数,如何巧妙的避开判断m的大小。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,md;
int pri[55];
int g[10001];
ll dp[55][5555];
void init()
{
for(int i=1;i<=49;i++) pri[i]=1;
pri[0]=0;pri[1]=0;
for(int i=2;i<=7;i++)
{
if(pri[i])
{
for(int j=i*i;j<=49;j+=i) pri[j]=0;
}
}
for(int i=1;i<=9999;i++) g[i]=g[i/10]+i%10;
}
ll dfs(int pos,int num)
{
if(pos==0) return 1;
ll &ans=dp[pos][num];
if(~ans) return ans;
ans=0;
for(int i=0;i<=9;i++)
{
if(pos+m-1>n||pri[g[num]+i]==1)
{
ans+=dfs(pos-1,(num*10+i)%md);
}
}
return ans;
… Read the rest