洛谷 P2359 分析（别看）

科技起源

2026-07-15 14:16:40

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

1.2 题目背景、允许、禁止与限制

背景：三素数数是指一个长度至少为 $3$ 的数字每相邻三位组成的三位数都是素数。
允许：给定一个数字 $n$ ，求合法 $n$ 位三素数数的数量
禁止：
限制：最终求数量 $mod~10^9+9$ 的具体值

1.3 题目数据范围与猜测

$1 \le n \le 10^4 \longrightarrow 严格小于O(n^2)$

1.4 一句话概括题意

给定一个数字 $n$ ，求合法 $n$ 位三素数数的数量

2 题目破题推导

2.1 数字关系

首先，我们假定一个 $n$ 位数字 $p=\overline{d_1d_2...d_{n-1}d_n}$
那么我们观察每两个三位数的关系：
$p_1=\overline{d_1d_2d_3}$ $p_2=\overline{d_2d_3d_4}$
我们发现重合的只有两位： $d_2$ 和 $d_3$ ，也就是两个三位数衔接起来需要保证：前一个三位数的后两位 $=$ 后一个三位数的前两位

2.2 转化为图论模型

节点定义：
把两位数 $\overline{ab}$ 作为节点
边定义：
由于刚刚我们发现了数字之间的关系，因此对于三位数 $\overline{abc}$
起点 $u$ 对应的节点就是 $\overline{ab}$ ，终点 $v$ 对应的节点就是 $\overline{bc}$
再建一条 $u \rightarrow v$ 的边，建边时注意当且仅当 $\overline{abc}$ 位素数时才能建

2.3 原问题转化

分情况

当 $n<3$ ：不存在
当 $n=3$ ：答案即所有三位素数的总数
当 $n>3$ ：既然已经建立了图，那么
一个 $n$ 位三素数数，等价于图中一条长度为 $n-2$ 的路径：
为什么会是这样，举个数量关系的例子：
当只有 $1$ 条边时，两端合并只有 $3$ 位数字；当只有 $2$ 条边时，两端合并只有 $4$ 位数字；
这样当只有 $k$ 条边时，两端合并只有 $k+2$ 位数字
题目要求 $n$ 位三素数数，解方程： $k+2=n$ ，求得 $k=n-2$
因此最终求的是长度为 $n-2$ 的路径的数量

素数我们在建边的时候已经考虑过了

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

我们发现，这个路径存在三个能够证明可以使用 $\huge{dp}$ 的点

路径计数具备无后效性，因为下一步能走到哪些节点只看当前考虑到的这个点，和前面怎么走的无关
路径计数具备重叠子问题，大量不同路径走完 $k-1$ 步后都会到同一节点
路径计数存在清晰递推关系：第 $k$ 步到达 $v$ 的路径，一定是一条第 $k-1$ 条到达 $u$ ，且 $u \rightarrow v$ 有这条合法边。

4 最终代码（禁止抄袭，仅用于参考）

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

int n;
const int N = 1e4 + 10, M = 100, K = 1000;
int dp[N][M];
const int MOD = 1e9 + 9;
bool is_prime(int x){
    for (int i = 2;i * i <= x;i++){
        if (x % i == 0){
            return false;
        }
    }
    return true;
}
vector<int> prime;
bool flag[K];
void init(){
    for (int i = 100;i <= 999;i++){
        if (is_prime(i)){
            prime.push_back(i);
            flag[i] = true;
        }
    }
}

int main(){

    init();
    cin >> n;
    for (int i = 0;i < prime.size();i++){
        int now = prime[i];
        int shi = (now / 10) % 10;
        int temp = shi * 10 + (now % 10);
        dp[3][temp]++;
        dp[3][temp] %= MOD;
    }
    for (int i = 4;i <= n;i++){
        for (int xy = 0;xy <= 99;xy++){
            if (dp[i - 1][xy] == 0){
                continue;
            }
            for (int z = 0;z <= 9;z++){
                int shi = (xy / 10) % 10;
                int ge = xy % 10;
                if (flag[shi * 100 + ge * 10 + z]){
                    dp[i][ge * 10 + z] += dp[i - 1][shi * 10 + ge];
                    dp[i][ge * 10 + z] %= MOD;
                }
            }
        }
    }
    if (n == 3){
        cout << prime.size();
        return 0;
    } else {
        int ans = 0;
        for (int i = 0;i <= 99;i++){
            ans += dp[n][i];
            ans %= MOD;
        }
        cout << ans; 
    }
    
    return 0;
}