原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个具体值
1.2 题目背景、允许、禁止与限制
背景：三素数数是指一个长度至少为 333 的数字每相邻三位组成的三位数都是素数。
允许：给定一个数字 nnn，求合法 nnn 位三素数数的数量
禁止：
限制：最终求数量 mod 109+9mod~10^9+9mod 109+9 的具体值
1.3 题目数据范围与猜测
1≤n≤104⟶严格小于O(n2)1 \le n \le 10^4 \longrightarrow 严格小于O(n^2)1≤n≤104⟶严格小于O(n2)
1.4 一句话概括题意
给定一个数字 nnn，求合法 nnn 位三素数数的数量
2 题目破题推导
2.1 数字关系
首先，我们假定一个 nnn 位数字 p=d1d2...dn−1dn‾p=\overline{d_1d_2...d_{n-1}d_n}p=d1 d2 ...dn−1 dn
那么我们观察每两个三位数的关系：
p1=d1d2d3‾p_1=\overline{d_1d_2d_3}p1 =d1 d2 d3 p2=d2d3d4‾p_2=\overline{d_2d_3d_4}p2 =d2 d3 d4
我们发现重合的只有两位：d2d_2d2 和 d3d_3d3 ，也就是两个三位数衔接起来需要保证：前一个三位数的后两位 === 后一个三位数的前两位
2.2 转化为图论模型
* 节点定义：
把两位数 ab‾\overline{ab}ab 作为节点
* 边定义：
由于刚刚我们发现了数字之间的关系，因此对于三位数 abc‾\overline{abc}abc
起点 uuu 对应的节点就是 ab‾\overline{ab}ab，终点 vvv 对应的节点就是 bc‾\overline{bc}bc
再建一条 u→vu \rightarrow vu→v 的边，建边时注意当且仅当 abc‾\overline{abc}abc 位素数时才能建
2.3 原问题转化
分情况
* 当 n<3n<3n<3：不存在
* 当 n=3n=3n=3：答案即所有三位素数的总数
* 当 n>3n>3n>3：既然已经建立了图，那么
一个 nnn 位三素数数，等价于图中一条长度为 n−2n-2n−2 的路径：
为什么会是这样，举个数量关系的例子：
当只有 111 条边时，两端合并只有 333 位数字；当只有 222 条边时，两端合并只有 444 位数字；
这样当只有 kkk 条边时，两端合并只有 k+2k+2k+2 位数字
题目要求 nnn 位三素数数，解方程：k+2=nk+2=nk+2=n，求得 k=n−2k=n-2k=n−2
因此最终求的是长度为 n−2n-2n−2 的路径的数量
素数我们在建边的时候已经考虑过了
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
我们发现，这个路径存在三个能够证明可以使用 dp\huge{dp}dp 的点
1. 路径计数具备无后效性，因为下一步能走到哪些节点只看当前考虑到的这个点，和前面怎么走的无关
2. 路径计数具备重叠子问题，大量不同路径走完 k−1k-1k−1 步后都会到同一节点
3. 路径计数存在清晰递推关系：第 kkk 步到达 vvv 的路径，一定是一条第 k−1k-1k−1 条到达 uuu，且 u→vu \rightarrow vu→v 有这条合法边。
4 最终代码（禁止抄袭，仅用于参考）
