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;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	ios::sync_with_stdio(false);
	cin>>n>>m;
	if(m>n) {
		cout<<0;
		return 0;
	}
	init();
	md=1;
	for(int i=1;i<m;i++)
	{
		md*=10;
	}
	cout<<dfs(n,0);     
}

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int pri[101]={0};
int n,m;
typedef long long ll;
//typedef int ll;
ll dp4[15][11][11][11]={0};
ll dp3[15][11][11]={0};
ll dp2[15][11]={0};
ll dp1[15]={0};

void gpri()
{
	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;	
		} 
	}
}
int main()
{
	ios::sync_with_stdio(false);
	gpri();
	cin>>n>>m;
	if(m>n||m==0)
	{
		cout<<0;
		return 0;
	}
	ll ans=0;
	if(m==1)
	{
		dp1[0]=1;
		for(int i=m;i<=n;i++)
		for(int j=0;j<=9;j++)
		if(pri[j]) dp1[i]+=dp1[i-1];
		ans=dp1[n];
	}
	if(m==2)
	{
		for(int i=0;i<=9;i++) dp2[1][i]=1;
		for(int i=m;i<=n;i++)
		for(int j=0;j<=9;j++)
		for(int k=0;k<=9;k++)
		if(pri[j+k]) dp2[i][k]+=dp2[i-1][j];
		for(int i=0;i<=9;i++) ans+=dp2[n][i];
	}
	if(m==3)
	{
		for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++) dp3[2][i][j]=1;
		for(int i=m;i<=n;i++)
		for(int j=0;j<=9;j++)
		for(int k=0;k<=9;k++)
		for(int l=0;l<=9;l++)
		if(pri[j+k+l]) dp3[i][l][k]+=dp3[i-1][k][j];
		for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++) ans+=dp3[n][i][j];
	}
	if(m==4)
	{
		for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++)
		for(int k=0;k<=9;k++) dp4[3][i][j][k]=1;
		for(int i=m;i<=n;i++)
		for(int j=0;j<=9;j++)
		for(int k=0;k<=9;k++)
		for(int l=0;l<=9;l++)
		for(int h=0;h<=9;h++)
		if(pri[j+k+l+h]) dp4[i][h][l][k]+=dp4[i-1][l][k][j];
		for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++)
		for(int k=0;k<=9;k++) ans+=dp4[n][i][j][k];
	}
	cout<<ans;	
} 
//第一次写的