#P3284. 第3题-小美的素数数组
-
1000ms
Tried: 12
Accepted: 6
Difficulty: 6
所属公司 :
美团
时间 :2025年5月31日-算法岗
-
算法标签>动态规划
第3题-小美的素数数组
题解
题目描述
小美有一个长度为 n 的序列 a,她希望序列中所有元素都是素数。她可以多次进行如下操作:
- 选择一对相邻的数字,将它们合并成一个数,结果为两者的和。
问:最终满足条件的序列(所有元素都是素数)有多少种不同的形态?结果对 109+7 取模。
解题思路
问题本质:将序列分割成若干连续子段,使得每个子段的和都是素数,求不同的分割方案数。
关键步骤:
- 预处理素数表:使用埃氏筛法预处理 0 到 4000000(最大可能的子段和)的素数标记数组。
- 动态规划:
- 定义 dp[i] 表示前 i 个元素的分割方案数。
- 初始化 dp[0]=1(空序列有一种分割方案)。
- 计算前缀和数组 prefix,其中 prefix[i]=a0+a1+⋯+ai−1。
- 对于每个位置 i(从 1 到 n),枚举所有可能的分割点 j(0≤j<i):
- 计算子段和 sum=prefix[i]−prefix[j]。
- 若 sum 是素数,则 dp[i]=(dp[i]+dp[j])mod109+7。
- 输出结果:dp[n] 即为最终答案。
时间复杂度:
- 预处理素数表:O(MAX_SUMloglogMAX_SUM)(MAX_SUM=4000000)
- 动态规划:每组数据 O(n2),总 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) ,将 ai 和 ai+1 合并为一个数字,结果是 ai+ai+1 。
小美想知道,如果要满足她的条件(即所有元素都是素数),则在她操作完后,a 有多少种可能的形态,请你帮她算一算吧。
(小美认为两个序列 a,b 的最终形态不同,当且仅当两个序列 a,b 的长度不同、或者长度相同且存在 i 使得 ai=bi 。)
输入描述
本题有多组测试数据。
输入的第一行包含一个正整数 T(1≤T≤100) ,表示数据组数。
接下来包含 T 组数据,每组数据的格式如下:
第一行一个正整数 n(1≤n≤2000) ,表示序列 a 的长度。
第二行 n 个正整数 ai(1≤ai≤2000) ,表示序列 a
(保证所有测试数据中,n 的总和不超过 2000 。)
输出描述
对于每组测试数据:
在单独的一行输出一个整数,表示最终符合条件的 a 的可能结果。
(由于结果可能很大,因此你只需要输出结果对 109+7 取模的值即可。)
样例1
输入
1
5
2 3 2 1 1
输出
5