日常水一篇（滑稽）
题目描述
如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。
输入输出格式
输入格式：
一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。
输出格式：
一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。
输入输出样例
输入样例#1：
4
输出样例#1：
204
题解
这题明显dp。
预处理素数表，这样可以
然后就是dp数组，一开始是这样的：f[10001]；
发现不够，改成这样：f[10001][10][10][10]；
发现有点多，不好写，又改少点：f[10001][10][10]
这就是最终的dp数组，f[i][j][k]代表第i位，素数第二位是j，素数第三位是k的方案数。
之后就是初始化，利用素数表初始化出f[3][a][b]的所有值。
然后一直递推就好了，不断枚举a,b,c，dp方程就是f[i][b][c]+=f[i-1][a][b]（a*100+b*10+c是素数）。
记得取模就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const int p=1000000009;
int prime[1000];
int vis[1000];
int n,cnt;
void init(){
for(int i=2;i<1000;i++){
if(!vis[i]){
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&i*prime[j]<1000;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
break;
}
}
}
}
int f[10001][10][10];
void dp(){
for(int a=1;a<=9;a++){
for(int b=1;b<=9;b++){
for(int c=1;c<=9;c++){
if(!vis[a*100+b*10+c]){
f[3][b][c]++;
}
}
}
}
for(int i=4;i<=n;i++){
for(int a=1;a<=9;a++){
for(int b=1;b<=9;b++){
for(int c=1;c<=9;c++){
if(!vis[a*100+b*10+c]){
f[i][b][c]=(f[i][b][c]+f[i-1][a][b])%p;
}
}
}
}
}
}
int main(){
scanf("%d",&n);
init();
dp();
int ans=0;
for(int b=1;b<=9;b++){
for(int c=1;c<=9;c++){
ans=(ans+f[n][b][c])%p;
}
}
printf("%d",ans);
return 0;
}