三素数数

GitHub跳转原题关系图返回列表

把最后两位数字当作状态，按位转移时只检查新形成的三位数是否为素数，从而用 O(n) 统计答案。

OJ: luogu

题目 ID: P2359

难度:普及+/提高

标签:动态规划素数数论dp

日期: 2026-06-19 13:36

目录

  1. 题意
  2. 思路
    1. 状态表
    2. DP 公式
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

如果一个 n 位数的每一个连续三位数字都是大于 100 的素数，那么它就是三素数数。

题目要求统计所有 n 位三素数数的个数，并对 10^9+9 取模。

思路

先看最直接的暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接枚举所有 n 位数，逐个检查每个长度为 3 的连续子串是否都是三位素数。

int n;
const int MOD = 1000000009;

bool check_prime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

bool check_number(int x) {
    string s = to_string(x);
    if ((int)s.size() != n) {
        return false;
    }
    for (int i = 0; i + 2 < n; i++) {
        int val = (s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
        if (val < 100 || !check_prime(val)) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    if (n < 3) {
        cout << 0 << '\n';
        return 0;
    }

    int start = 1;
    for (int i = 1; i < n; i++) {
        start *= 10;
    }
    int finish = start * 10 - 1;

    int ans = 0;
    for (int x = start; x <= finish; x++) {
        if (check_number(x)) {
            ans++;
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}

下面是另一种「选择序列」风格的暴力写法。它按位依次决定当前数字填什么，递归生成完整数字后，叶子节点再统一检查每个三位窗口是否为素数：

另一种暴力写法：选择序列
cpp
// brute_01_style.cpp：选择序列风格暴力，按位决定当前数字填什么。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MOD = 1000000009;

int n;
int digit[MAXN];
int answer;

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

bool check() {
    if (digit[1] == 0) return false;
    for (int i = 3; i <= n; i++) {
        int val = digit[i - 2] * 100 + digit[i - 1] * 10 + digit[i];
        if (val < 100 || !is_prime(val)) return false;
    }
    return true;
}

void dfs_build(int pos) {
    if (pos == n + 1) {
        if (check()) {
            answer++;
            if (answer >= MOD) {
                answer -= MOD;
            }
        }
        return;
    }

    // 第 pos 位可以填 0..9；完整生成后再统一检查。
    for (int d = 0; d <= 9; d++) {
        digit[pos] = d;
        dfs_build(pos + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    if (n < 3) {
        cout << 0 << '\n';
        return 0;
    }

    answer = 0;
    dfs_build(1);

    cout << answer << '\n';
    return 0;
}

brute.cpp 会枚举所有 n 位数，然后逐个检查每一段长度为 3 的连续子串是否都是素数。

这个做法很容易理解，但复杂度接近 10^n，位数稍大就不可用了。

关键观察是：当我们已经确定了当前数的最后两位 ab，再接下一位 d 时，新产生的唯一约束就是：

  • abd 这个三位数是否为素数

更前面的数字已经不会再影响后续。

于是设：

  • dp[len][ab] 表示长度为 len、最后两位是 ab 的三素数数个数

初始化时，所有三位素数本身都可以作为一个长度为 3 的合法起点。

之后枚举当前末尾两位 ab 和下一位 d：

  • 如果 ab * 10 + d 是三位素数
  • 就可以转移到新的末尾 bd

状态表

这张表展示状态含义：

状态 含义
dp[len][ab] 长度为 len，最后两位是 ab 的三素数数个数

因为末尾两位只有 00..99 共 100 种，所以状态数非常小。
再加上 n 只到 10^4，直接按长度递推并滚动数组就够了。

DP 公式

设 dplen,abdp_{len,ab} 表示长度为 lenlen、最后两位为 abab 的三素数数个数。若接上一位数字 dd 后，三位数 10ab+d10ab+d 是素数，则：

dplen+1, 10(b)+d+=dplen,ab dp_{len+1,\ 10(b)+d}\mathrel{+}=dp_{len,ab}

其中更直观地写，若 abab 的十位为 aa、个位为 bb，新末尾就是 bdbd。初始化为所有三位素数：

dp3, p mod 100+=1(p 是三位素数) dp_{3,\ p\bmod 100}\mathrel{+}=1\quad (p\text{ 是三位素数})

最终答案为：

∑ab=099dpn,ab \sum_{ab=0}^{99} dp_{n,ab}

公式解释：每次新接一位后，只有最新形成的三位数需要检查是否为素数。更早的三位窗口已经在前面检查过，所以保留最后两位作为状态就足够。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXS = 100;
const int MOD = 1000000009;

int n;
bool is_prime[1000];
int dp[MAXS], ndp[MAXS]; // dp[ab]：当前长度下，最后两位是 ab 的方案数

bool check_prime(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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 100; i <= 999; i++) {
        is_prime[i] = check_prime(i);
    }

    if (n < 3) {
        cout << 0 << '\n';
        return 0;
    }

    // 长度为 3 时，所有三位素数都可以作为起点。
    for (int x = 100; x <= 999; x++) {
        if (!is_prime[x]) {
            continue;
        }
        int last2 = x % 100;
        dp[last2]++;
    }

    for (int len = 4; len <= n; len++) {
        for (int i = 0; i <= 99; i++) {
            ndp[i] = 0;
        }
        for (int ab = 0; ab <= 99; ab++) {
            if (dp[ab] == 0) {
                continue;
            }
            for (int d = 0; d <= 9; d++) {
                int num = ab * 10 + d;
                if (!is_prime[num]) {
                    continue;
                }
                int next_last2 = num % 100;
                ndp[next_last2] = (ndp[next_last2] + dp[ab]) % MOD;
            }
        }
        for (int i = 0; i <= 99; i++) {
            dp[i] = ndp[i];
        }
    }

    int ans = 0;
    for (int ab = 0; ab <= 99; ab++) {
        ans += dp[ab];
        if (ans >= MOD) {
            ans -= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(n∗100∗10)O(n * 100 * 10)，可以看作 O(n)O(n)
  • 空间复杂度：O(100)O(100)

总结

这题的关键是看出“三位窗口”每次右移一位后，只会留下后两位继续参与下一次判断。

一旦把这个后缀信息提成状态，整题就自然变成了一个很小的按位 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析