题目描述
如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。
输入输出格式
输入格式：
一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。
输出格式：
一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。
输入输出样例
输入样例#1： 复制
4
输出样例#1： 复制
204
说明
区域动归QAQ
.
.
.
.
.
程序：
#include<bits/stdc++.h>
using namespace std;
long long f[10001][11][11],ans=0,n;
bool check(int x)
{
if(x==1) return(false);
int mid=sqrt(x);
for (int i=2;i<=mid;i++)
if (x % i ==0) return(false);
return(true);
}
int main()
{
memset(f,0,sizeof(f));
for (int i=1; i<=9;i++)
for (int j=1; j<=9;j++)
{
int tmp=0;
for (int k=1; k<=9;k++)
if (check(100*k+10*i+j)) tmp++;
f[3][i][j]=tmp;
}
scanf("%lld",&n);
for (int i=4; i<=n;i++)
for (int k=1; k<=9;k++)
for (int e=1; e<=9;e++)
{
for (int j=1;j<=9;j++)
if (check(100*j+10*e+k)) f[i][e][k]=(f[i][e][k]+f[i-1][j][e]) % 1000000009;
}
for (int i=1;i<=9;i++)
for (int j=1;j<=9;j++)
ans=(ans+f[n][i][j]) % 1000000009;
printf("%lld
",ans);
}