题解

题目描述

小美有一个长度为 $n$ 的序列 $a$，她希望序列中所有元素都是素数。她可以多次进行如下操作：

• 选择一对相邻的数字，将它们合并成一个数，结果为两者的和。

问：最终满足条件的序列（所有元素都是素数）有多少种不同的形态？结果对 $10^9+7$ 取模。

解题思路

问题本质：将序列分割成若干连续子段，使得每个子段的和都是素数，求不同的分割方案数。

关键步骤：

1. 预处理素数表：使用埃氏筛法预处理 $0$ 到 $4000000$（最大可能的子段和）的素数标记数组。
2. 动态规划：
   • 定义 $dp[i]$ 表示前 $i$ 个元素的分割方案数。
   • 初始化 $dp[0] = 1$（空序列有一种分割方案）。
   • 计算前缀和数组 $prefix$，其中 $prefix[i] = a_0 + a_1 + \dots + a_{i-1}$。
   • 对于每个位置 $i$（从 $1$ 到 $n$），枚举所有可能的分割点 $j$（$0 \leq j < i$）：
     • 计算子段和 $sum = prefix[i] - prefix[j]$。
     • 若 $sum$ 是素数，则 $dp[i] = (dp[i] + dp[j]) \mod 10^9+7$。
3. 输出结果：$dp[n]$ 即为最终答案。

时间复杂度：

• 预处理素数表：$O(\text{MAX\_SUM} \log \log \text{MAX\_SUM})$（$\text{MAX\_SUM}=4000000$）
• 动态规划：每组数据 $O(n^2)$，总 $n$ 不超过 $2000$，可接受。

C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 1e9+7;
const int MAX_SUM = 4000000; // 最大子段和：2000*2000=4000000

vector<bool> is_prime; // 素数标记数组

// 预处理素数表（埃氏筛）
void init_prime() {
    is_prime.resize(MAX_SUM+1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= MAX_SUM; i++) {
        if (is_prime[i]) {
            if ((long long)i * i > MAX_SUM) break; // 防止溢出
            for (int j = i*i; j <= MAX_SUM; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init_prime(); // 初始化素数表

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 计算前缀和
        vector<long long> prefix(n+1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i+1] = prefix[i] + a[i];
        }

        // dp[i]：前i个元素的分割方案数
        vector<long long> dp(n+1, 0);
        dp[0] = 1; // 空序列方案数为1

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                long long seg_sum = prefix[i] - prefix[j]; // 子段和
                if (seg_sum <= MAX_SUM && is_prime[seg_sum]) {
                    dp[i] = (dp[i] + dp[j]) % MOD; // 转移
                }
            }
        }

        cout << dp[n] % MOD << "\n";
    }

    return 0;
}

Python

MOD = 10**9 + 7
MAX_SUM = 4000000

# 预处理素数表（埃氏筛）
def init_prime():
    is_prime = [True] * (MAX_SUM + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, MAX_SUM + 1):
        if is_prime[i]:
            if i * i > MAX_SUM:
                break
            for j in range(i * i, MAX_SUM + 1, i):
                is_prime[j] = False
    return is_prime

is_prime = init_prime()

import sys

def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    index = 1
    results = []
    for _ in range(t):
        n = int(data[index])
        index += 1
        a = list(map(int, data[index:index + n]))
        index += n
        
        # 计算前缀和
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + a[i - 1]
        
        # dp[i]：前i个元素的分割方案数
        dp = [0] * (n + 1)
        dp[0] = 1  # 空序列方案数为1
        
        for i in range(1, n + 1):
            for j in range(0, i):
                seg_sum = prefix[i] - prefix[j]  # 子段和
                if seg_sum <= MAX_SUM and is_prime[seg_sum]:
                    dp[i] = (dp[i] + dp[j]) % MOD  # 转移
        
        results.append(str(dp[n] % MOD))
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int)1e9 + 7;
    static final int MAX_SUM = 4000000;
    static boolean[] isPrime; // 素数标记数组

    // 预处理素数表（埃氏筛）
    static void initPrime() {
        isPrime = new boolean[MAX_SUM + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= MAX_SUM; i++) {
            if (isPrime[i]) {
                if ((long)i * i > MAX_SUM) break; // 防止溢出
                for (int j = i * i; j <= MAX_SUM; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        initPrime(); // 初始化素数表
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] aLine = br.readLine().split(" ");
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(aLine[i]);
            }

            // 计算前缀和
            long[] prefix = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                prefix[i] = prefix[i - 1] + a[i - 1];
            }

            // dp[i]：前i个元素的分割方案数
            long[] dp = new long[n + 1];
            dp[0] = 1; // 空序列方案数为1

            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < i; j++) {
                    long segSum = prefix[i] - prefix[j]; // 子段和
                    if (segSum <= MAX_SUM && isPrime[(int)segSum]) {
                        dp[i] = (dp[i] + dp[j]) % MOD; // 转移
                    }
                }
            }

            sb.append(dp[n] % MOD).append("\n");
        }
        System.out.print(sb);
    }
}

题目内容

小美有一个长度为 $n$ 的序列 $a$ ，但小美只对素数感兴趣，因此小美希望 $a$ 中所有的元素都是素数。为此，小美可以做如下的操作任意次：

• 选择一对相邻的数字，将他们合并成一个数，结果为两者的和。

  (形式化的：选择 $i(1≤i<n)$ ，将 $a_i$ 和 $a_{i+1}$ 合并为一个数字，结果是 $a_i+a_{i+1}$ 。

小美想知道，如果要满足她的条件(即所有元素都是素数)，则在她操作完后，$a$ 有多少种可能的形态，请你帮她算一算吧。

(小美认为两个序列 $a,b$ 的最终形态不同，当且仅当两个序列 $a,b$ 的长度不同、或者长度相同且存在 $i$ 使得 $a_i ≠b_i$ 。)

输入描述

本题有多组测试数据。

输入的第一行包含一个正整数 $T(1≤T≤ 100)$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行一个正整数 $n(1≤n≤2000)$ ，表示序列 $a$ 的长度。

第二行 $n$ 个正整数 $a_i(1≤a_i≤2000)$ ，表示序列 $a$

(保证所有测试数据中，$n$ 的总和不超过 $2000$ 。)

输出描述

对于每组测试数据：

在单独的一行输出一个整数，表示最终符合条件的 $a$ 的可能结果。

(由于结果可能很大，因此你只需要输出结果对 $10^9+7$ 取模的值即可。)

样例1

输入

1
5
2 3 2 1 1

输出

5