如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。
URAL/1586
来自"NOCOW"
< URAL
水DP，不想优化了，反正ural电脑配置好。。。
#include <cstdio> #include <cstdlib> #include <cstring> #define count(x,y,z) ((x*100)+(y*10)+z) const int mod=1000000009; int n,tot=0,now=0,ans=0,s[10][10],t[2][10][10][10]={0}; bool p[1000]={false}; int get(int x,int y) { for (;y;x/=10,--y); return x%10; } int main() { scanf("%d",&n); for (int i=2;i<1000;++i) if (!p[i]) for (int j=i*i;j<1000;j+=i) p[j]=true; p[0]=p[1]=true; for (int i=100;i<1000;++i) if (!p[i]) t[now][get(i,2)][get(i,1)][get(i,0)]=1; for (int m=4;m<=n;++m) { now^=1; memset(t[now],0,sizeof(t[now])); memset(s,0,sizeof(s)); for (int i=0;i<10;++i) for (int j=0;j<10;++j) for (int k=0;k<10;++k) s[i][j]=(s[i][j]+t[now^1][i][j][k])%mod; for (int i=1;i<10;++i) for (int j=0;j<10;++j) for (int k=0;k<10;++k) if (!p[count(i,j,k)]) t[now][i][j][k]=(t[now][i][j][k]+s[j][k])%mod; } for (int i=1;i<10;++i) for (int j=0;j<10;++j) for (int k=0;k<10;++k) ans=(ans+t[now][i][j][k])%mod; printf("%d\n",ans); return 0; } //by zzy
