18025 小明的密码
时间限制:4000MS 内存限制:65535K
提交次数:0 通过次数:0题型: 编程题 语言: G++;GCC
Description
小明的密码由N（1<=N<=12）个数字构成，每个数字都可以是0至9中任意一个数字，但小明的密码还有
一个特点就是密码中连续的M（1<=M<=4）个数字的和是质数，现给定M和N，求满足条件的密码共有多少
个？输入格式
第1行是T，case数量，此后T行，每行两个数，N和M输出格式
每个case输出一个满足条件的密码总数输入样例
2
1 1
2 1输出样例
4
16
这题数据很小，可以直接DFS暴力求解，但是有更好的DP思路。。不过代码略长dp[i][j][k][z],i表示当前是几位数,j表示当前这个数的最后一位,k,z分别是倒数二、三位。
假设M=4时.如果j+k+z+a是素数的时候，dp[i-1][k][z][a]可以推出dp[i][j][k][z],也就是dp[i][j][k][z]+=dp[i-1][k][z][a];
这样一来，我们就可以用暴力的方法求出dp[4][j][k][z]，然后递推上去。时间复杂度是n*10^m
下面是代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
typedef long long ll;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))
#define ss(x) scanf("%s",(x))
#define maxn 1000000
#include <ctime>
//如果是学校的同学要把这个删掉，因为学校OJ禁了time头文件.
const int inf=0x3f3f3f3f;
const long long mod=;
using namespace std;
int dp[][][][];
long long ans[][];
bool prime[];
void get_prime()
{
prime[]=prime[]=;
for(int i=;i<=;i++)
{
if(!prime[i])
{
for(int j=i+i;j<=;j+=i)
prime[j]=;
}
}
}
void init()
{
ans[][]=;
//M=1
for(int i=;i<=;i++)
ans[i][]=ans[i-][]*;
//M=2
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(!prime[i+j])
dp[][][][i]++;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
if(!prime[j+k])
dp[i][][][j]+=dp[i-][][][k];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
ans[i][]+=dp[i][][][j]; //M=3
memset(dp,,sizeof dp);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
if(!prime[i+j+k])
dp[][][i][j]++;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
for(int z=;z<=;z++)
if(!prime[j+k+z])
dp[i][][j][k]+=dp[i-][][k][z];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
ans[i][]+=dp[i][][j][k]; //M=4
memset(dp,,sizeof dp);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
for(int z=;z<=;z++)
if(!prime[i+j+k+z])
dp[][i][j][k]++;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
for(int z=;z<=;z++)
for(int a=;a<=;a++)
if(!prime[j+k+z+a])
dp[i][j][k][z]+=dp[i-][k][z][a];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
for(int a=;a<=;a++)
ans[i][]+=dp[i][j][k][a];
}
int main()
{
#ifdef local
freopen("in","r",stdin);
//freopen("out","w",stdout);
int _time=clock();
#endif
get_prime();
init();
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
cout<<ans[n][m]<<endl;
}
#ifdef local
printf("time: %d\n",int(clock()-_time));
#endif
}