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=1000000007; using namespace std; int dp[15][10][10][10]; long long ans[15][5]; bool prime[100]; void get_prime() { prime[0]=prime[1]=1; for(int i=2;i<=40;i++) { if(!prime[i]) { for(int j=i+i;j<=40;j+=i) prime[j]=1; } } } void init() { ans[0][1]=1; //M=1 for(int i=1;i<=12;i++) ans[i][1]=ans[i-1][1]*4; //M=2 for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) if(!prime[i+j]) dp[2][0][0][i]++; for(int i=3;i<=12;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(!prime[j+k]) dp[i][0][0][j]+=dp[i-1][0][0][k]; for(int i=1;i<=12;i++) for(int j=0;j<=9;j++) ans[i][2]+=dp[i][0][0][j]; //M=3 memset(dp,0,sizeof dp); for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(!prime[i+j+k]) dp[3][0][i][j]++; for(int i=4;i<=12;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int z=0;z<=9;z++) if(!prime[j+k+z]) dp[i][0][j][k]+=dp[i-1][0][k][z]; for(int i=1;i<=12;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) ans[i][3]+=dp[i][0][j][k]; //M=4 memset(dp,0,sizeof dp); for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int z=0;z<=9;z++) if(!prime[i+j+k+z]) dp[4][i][j][k]++; for(int i=5;i<=12;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int z=0;z<=9;z++) for(int a=0;a<=9;a++) if(!prime[j+k+z+a]) dp[i][j][k][z]+=dp[i-1][k][z][a]; for(int i=1;i<=12;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int a=0;a<=9;a++) ans[i][4]+=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 ",int(clock()-_time)); #endif }