题解 P2359 【三素数数】

· · 题解

题意：

三素数数，指这个数的每连续3位数都是质数。

问在长度为n的所有数中，有多少个三素数数？

题解思路：

由于n非常的大，所以不能通过暴力枚举+check的方式通过此题（不然就是红题了

所以我采用了DP（动态规划）

有题意可以得到，如果保证前面的数都满足三素数数，那么在这个数后面加上一个数，只要满足后三位数位是素数，则可以判断这个新数为三素数数，那么我们就可以使用递归，时间复杂度为O(n)，用f[i][j][k]表示当数位为i，倒数第二位为j，最后一位为k时的三素数数数量(滑稽

可以推出dp方程：if：a*100+j*10+k是素数（a为在这个三素数数倒数第三位的数），则f[i][j][k]+=f[i-1][a][j];

最后我们只要统计f[n][j][k]的所有和即可

别忘了每次都取模1000000009

代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
long long f[10010][15][15];
int vis[1010];
int a[200]={101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
//将所有三位素数全部存下来打表，只用判断一下就可以了（能节省一些时间
int main()
{
    memset(f,0,sizeof f);
    memset(vis,0,sizeof vis);
    int n;
    cin>>n;
    for(int i=0;i<143;i++) vis[a[i]]=1;
    for(int i=0;i<143;i++)
    {
        int b=a[i]/10;
        f[3][b%10][a[i]%10]++;//将三位素数提前预处理
    }
    long long Max=0;
    for(int i=4;i<=n;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                for(int a=0;a<=9;a++)
                {
                    if(vis[a*100+j*10+k]==1) f[i][j][k]+=f[i-1][a][j];
                    //dp转换方程
                    f[i][j][k]%=1000000009;
                    //别忘了取模
                }
            }
        }
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<=9;j++)
        {
            Max+=f[n][i][j];//统计和
        Max%=1000000009;//别忘了取模     
    }
    cout<<Max;//输出即可
    return 0;
}