洛谷 题解 P2359 【三素数数】

做\(DP\)题，无疑要考虑如下几点：

\(1.\)状态定义

\(2.\)状态转移方程

\(3.\)边界

\(4.\)目标

那我们来依次分析。

状态定义

\(f_{i,j,k}\)：第\(i\)位数，最后两位为\(j\)、\(k\)，的三素数数个数。

状态转移方程

首先，我们知道\(j\)，\(k\)，即个位和十位，所以我们考虑枚举百位，设百位为\(l\)，则有：

\(f_{i,j,k}=\sum{f_{i-1,l,j}}(\overline{ljk}\) \(is\) \(prime\) \()\)

但是要注意，百位不能为\(0\)，所以\(1<=l<=9\)

边界

这一点有些复杂，我稍微讲仔细点。

首先，有答案的时候肯定是\(n>=3\)，所以我们可以考虑初始化\(f_{2,i,j}\)。

由于答案为累加，所以\(f_{2,i,j}=1\)。

但是！

\(i\)可能为\(0\)吗？

所以这是一个坑点。。。

但是\(j\)可以取\(0\)。

目标

肯定是\(\sum{f_{n,i,j}}\) 喽。

\(AC\) \(Code\)

#include <iostream>
#include <cmath>
using namespace std;

const int Mod = 1e9 + 9;

int n, f[10010][11][11], ans;

bool is_prime(int x) {
    if (x == 0 || x == 1) return false;
    for (int i=2; i<=sqrt(x); i++)
        if (x % i == 0) return false;
    return true;
}

int main() {
    cin >> n;
    for (int i=1; i<=9; i++)
        for (int j=0; j<=9; j++)
            f[2][i][j] = 1;
    for (int i=3; i<=n; i++)
        for (int j=0; j<=9; j++)
            for (int k=0; k<=9; k++)
                for (int l=1; l<=9; l++)
                    if (is_prime(l*100 + j*10 + k)) f[i][j][k] = (f[i][j][k] + f[i-1][l][j]) % Mod;
    for (int i=0; i<=9; i++)
        for (int j=0; j<=9; j++)
            ans = (ans + f[n][i][j]) % Mod;
    cout << ans << endl;
    return 0;
}

洛谷 题解 P2359 【三素数数】

原文：https://www.cnblogs.com/zyh-cr7/p/12237193.html