原题链接

一道比较基础的 $\text{dp}$。

$dp_{i,j,k}$ 表示考虑前 $i$ 位，满足条件且第 $i$ 位为 $j$，第 $i-1$ 位为 $k$ 的情况总数。

考虑当前的 $i$ 位数是由 $i-1$ 位数加一位得来，容易得出转移方程：

$$dp_{i,j,k}=\sum^9_{p=1}[\overline{pkj}为素数]dp_{i-1,k,p}$$

答案即为所有满足条件且是 $n$ 位的数。

$$ans=\sum^9_{i=0}\sum^9_{j=0}dp_{n,i,j}$$

时间复杂度 $O(1000n)$。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=10100,M=210,W=15,K=1100;
const ll MOD=1e9+9;
ll dp[N][W][W],ans;
int n,prime[M],k;
bool flag[K];
bool check(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=101;i<=999;i+=2)//预处理三位数质数 
    {
        if(check(i))
        {
            prime[++k]=i;
            dp[3][i/10%10][i%10]++;
            flag[i]=true;
        }
    }
    for(int i=4;i<=n;i++)
    {
        for(int j=0;j<=9;j++)//第i位 
        {
            for(int e=0;e<=9;e++)//第i-1位 
            {
                for(int o=0;o<=9;o++)//第i-2位 
                {
                    if(flag[o*100+j*10+e]) dp[i][j][e]=(dp[i][j][e]+dp[i-1][o][j])%MOD;
                }
            }
        }
    }
    for(int i=0;i<=9;i++)
    {
        for(int j=0;j<=9;j++) ans=(ans+dp[n][i][j])%MOD;
    }
    printf("%lld",ans);
    return 0;
}