题目链接
洛谷 P2359 三素数数 题解
思路分析
首先，由于三素数数每相邻三位都是质数，所以我们猜测应该先预处理出所有三位的质数。然后，我们发现，要保证每相邻三位都是质数，那么一个 \(n\) 位三素数数可以看作在保证前面 \(n-1\) 位都是三素数数的基础上，在后面加上一个一位数使最后三位也是质数。所以，我们定义 \(dp_{i,j}\) 表示 \(i\) 位，末两位是 \(j\) 的三素数数的个数，然后寻找其与 \(i-1\) 位的三素数数个数的关系即可。
按前文所说，我们先预处理出所有三位数的素数，按末两位存进 \(100\) 个 vector 中，然后对于 \(dp_{i,j}\)，遍历所有末两位为 \(j\) 的素数 \(k\)，则 \(dp_{i,j}=\sum dp_{i-1,k/10}\)，其中 / 号为整除。
代码如下，时间复杂度为 \(O(n\sqrt{n}+nm)\)，其中 \(m\) 为三位素数个数，瓶颈在预处理素数，可以用素数筛法优化。
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=1e4+10,mod=1e9+9;
int n;
int dp[N][100];
vector<int> primes[100];bool isPrime(int x){ // 判断素数if (x<2) return 0;for (int i=2;i*i<=x;++i){if (x%i==0) return 0;}return 1;
}
int main(){scanf("%d",&n);for (int i=100;i<=999;++i){ // 预处理素数if (isPrime(i)) primes[i%100].push_back(i),++dp[3][i%100];}for (int i=4;i<=n;++i){for (int j=0;j<=99;++j){for (auto k:primes[j]) dp[i][j]=(dp[i][j]+dp[i-1][k/10])%mod; // mod!!!}}int ans=0;for (int i=0;i<=99;++i) ans=(ans+dp[n][i])%mod; // 还要 mod!!!printf("%d",ans);return 0;
}