Ural 1586 Threeprime Numbers：三位素數構造的 n 位數計數 DP

問題描述

稱一個 n 位數為「threeprime」，若其任意連續三位構成的三位數均為素數（首位不為 0）。求 n 位 threeprime 數的個數模 10⁹+9。（n ≤ 10000）

狀態定義

由於只關心連續三位，DP 狀態只需記錄最後兩位數字：

dp[i][j][k] = 長度為 i、倒數第二位為 j、最後一位為 k 的合法數字個數。

預處理三位素數

枚舉所有三位數 abc（a∈[1,9], b,c∈[0,9]），判斷是否為素數，存入 prime[a][b][c]。

狀態轉移

對於長度 i (≥4)，新增一位 h，新狀態 dp[i][k][h] 由所有滿足 prime[j][k][h] 的 dp[i-1][j][k] 轉移而來：

for (int i = 4; i <= n; ++i)
  for (int j = 0; j <= 9; ++j)
    for (int k = 0; k <= 9; ++k)
      for (int h = 0; h <= 9; ++h)
        if (prime[j][k][h]) {
            dp[i][k][h] = (dp[i][k][h] + dp[i-1][j][k]) % MOD;
        }

初始化

長度 3 時直接統計：dp[3][j][k] += prime[i][j][k]（i 1~9）。

答案計算

對所有 dp[n][i][j] 求和模 MOD。

複雜度

• 狀態數：n × 10 × 10 = 10⁶（n ≤ 10000）。
• 轉移：每狀態嘗試 10 個下一位，總操作 ~10⁷，極快。
• 空間：滾動數組可優化至 O(100)。

關鍵代碼

const int MOD = 1e9+9;
int prime[10][10][10], dp[10001][10][10];
int main() {
    // 預處理 prime
    for (int i=1;i<=9;++i)
      for (int j=0;j<=9;++j)
        for (int k=1;k<=9;++k) {
            int x = i*100+j*10+k;
            bool isp = true;
            for (int d=2; d*d<=x; ++d) if (x%d==0) { isp=false; break; }
            if (isp) prime[i][j][k] = 1;
        }
    // 初始化 dp[3]
    for (int i=1;i<=9;++i)
      for (int j=0;j<=9;++j)
        for (int k=1;k<=9;++k)
          dp[3][j][k] += prime[i][j][k];
    // DP
    int n; scanf("%d",&n);
    for (int i=4;i<=n;++i) { /* 上述四重循環 */ }
    // 統計答案
    int ans = 0;
    for (int i=0;i<=9;++i) for (int j=0;j<=9;++j) ans = (ans + dp[n][i][j]) % MOD;
    printf("%d\n", ans);
    return 0;
}

這是一道典型的「有限狀態自動機 + DP」問題，狀態壓縮到最後兩位，轉移由預處理的合法三元組決定。