题目链接：
题解：dp[i][j][k]表示长度为i,最高位为j,次高位为k的合法方案数，转移方程为当j*100+k*10+l为质数时dp[i][j][k]+=dp[i-1][k][l];
#include#include #include #include #include #include #define pb push_back#define ll long long#define PI 3.14159265#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define eps 1e-7typedef unsigned long long ull;const int mod=1e9+9;const int maxn=1e4+5;const int root=1e6+7;using namespace std;int t,cnt,n,m,k;bool prime[1000];ll dp[maxn][10][10];void init(){ for(int i=2;i<1000;i++) { if(!prime[i]) { for(int j=i*2;j<1000;j+=i) { prime[j]=true; } } } for(int i=0;i<10;i++) for(int j=0;j<10;j++) { dp[2][i][j]=1; }}int main(){ std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<10;++j) for(int k=0;k<10;k++) for(int l=0;l<10;l++) { if(!prime[j*100+k*10+l]) { dp[i][j][k]+=dp[i-1][k][l]; dp[i][j][k]%=mod; } } ll ans=0; for(int i=1;i<10;i++) for(int j=0;j<10;j++) { ans+=dp[n][i][j]; ans%=mod; } cout< <