题解\n\n### 题目描述\n小明有一个长度为 $n$ 的序列 $a$，他希望序列中所有元素都是纯粹数。他可以多次进行如下操作：\n- 选择一对相邻的数字，将它们合并成一个数，结果为两者的和。\n\n问：最终满足条件的序列（所有元素都是纯粹数）有多少种不同的形态？结果对 $10^9+7$ 取模。\n\n### 解题思路\n问题本质：将序列分割成若干连续子段，使得每个子段的和都是纯粹数，求不同的分割方案数。\n\n关键步骤：\n1. 预处理纯粹数表：使用埃氏筛法预处理 $0$ 到 $4000000$（最大可能的子段和）的纯粹数标记数组。\n2. 动态规划：\n - 定义 $dp[i]$ 表示前 $i$ 个元素的分割方案数。\n - 初始化 $dp[0] = 1$（空序列有一种分割方案）。\n - 计算前缀和数组 $prefix$，其中 $prefix[i] = a_0 + a_1 + \dots + a_{i-1}$。\n - 对于每个位置 $i$（从 $1$ 到 $n$），枚举所有可能的分割点 $j$（$0 \leq j < i$）：\n - 计算子段和 $sum = prefix[i] - prefix[j]$。\n - 若 $sum$ 是纯粹数，则 $dp[i] = (dp[i] + dp[j]) \mod 10^9+7$。\n3. 输出结果：$dp[n]$ 即为最终答案。\n\n时间复杂度：\n- 预处理纯粹数表：$O(\text{MAX\_SUM} \log \log \text{MAX\_SUM})$（$\text{MAX\_SUM}=4000000$）\n- 动态规划：每组数据 $O(n^2)$，总 $n$ 不超过 $2000$，可接受。\n\n### C++\ncpp\n#include <iostream>\n#include <vector>\n#include <cstring>\nusing namespace std;\n\nconst int MOD = 1e9+7;\nconst int MAX_SUM = 4000000; // 最大子段和：2000*2000=4000000\n\nvector<bool> is_prime; // 纯粹数标记数组\n\n// 预处理纯粹数表（埃氏筛）\nvoid init_prime() {\n is_prime.resize(MAX_SUM+1, true);\n is_prime[0] = false;\n is_prime[1] = false;\n for (int i = 2; i <= MAX_SUM; i++) {\n if (is_prime[i]) {\n if ((long long)i * i > MAX_SUM) break; // 防止溢出\n for (int j = i*i; j <= MAX_SUM; j += i) {\n is_prime[j] = false;\n }\n }\n }\n}\n\nint main() {\n ios_base::sync_with_stdio(false);\n cin.tie(nullptr);\n init_prime(); // 初始化纯粹数表\n\n int T;\n cin >> T;\n while (T--) {\n int n;\n cin >> n;\n vector<int> a(n);\n for (int i = 0; i < n; i++) {\n cin >> a[i];\n }\n\n // 计算前缀和\n vector<long long> prefix(n+1, 0);\n for (int i = 0; i < n; i++) {\n prefix[i+1] = prefix[i] + a[i];\n }\n\n // dp[i]：前i个元素的分割方案数\n vector<long long> dp(n+1, 0);\n dp[0] = 1; // 空序列方案数为1\n\n for (int i = 1; i <= n; i++) {\n for (int j = 0; j < i; j++) {\n long long seg_sum = prefix[i] - prefix[j]; // 子段和\n if (seg_sum <= MAX_SUM && is_prime[seg_sum]) {\n dp[i] = (dp[i] + dp[j]) % MOD; // 转移\n }\n }\n }\n\n cout << dp[n] % MOD << "\n";\n }\n\n return 0;\n}\n\n### Python\npython\nMOD = 10**9 + 7\nMAX_SUM = 4000000\n\n# 预处理纯粹数表（埃氏筛）\ndef init_prime():\n is_prime = [True] * (MAX_SUM + 1)\n is_prime[0] = is_prime[1] = False\n for i in range(2, MAX_SUM + 1):\n if is_prime[i]:\n if i * i > MAX_SUM:\n break\n for j in range(i * i, MAX_SUM + 1, i):\n is_prime[j] = False\n return is_prime\n\nis_prime = init_prime()\n\nimport sys\n\ndef main():\n data = sys.stdin.read().split()\n t = int(data[0])\n index = 1\n results = []\n for _ in range(t):\n n = int(data[index])\n index += 1\n a = list(map(int, data[index:index + n]))\n index += n\n \n # 计算前缀和\n prefix = [0] * (n + 1)\n for i in range(1, n + 1):\n prefix[i] = prefix[i - 1] + a[i - 1]\n \n # dp[i]：前i个元素的分割方案数\n dp = [0] * (n + 1)\n dp[0] = 1 # 空序列方案数为1\n \n for i in range(1, n + 1):\n for j in range(0, i):\n seg_sum = prefix[i] - prefix[j] # 子段和\n if seg_sum <= MAX_SUM and is_prime[seg_sum]:\n dp[i] = (dp[i] + dp[j]) % MOD # 转移\n \n results.append(str(dp[n] % MOD))\n \n print("\n".join(results))\n\nif __name__ == "__main__":\n main()\n\n### Java\njava\nimport java.util.*;\nimport java.io.*;\n\npublic class Main {\n static final int MOD = (int)1e9 + 7;\n static final int MAX_SUM = 4000000;\n static boolean[] isPrime; // 纯粹数标记数组\n\n // 预处理纯粹数表（埃氏筛）\n static void initPrime() {\n isPrime = new boolean[MAX_SUM + 1];\n Arrays.fill(isPrime, true);\n isPrime[0] = false;\n isPrime[1] = false;\n for (int i = 2; i <= MAX_SUM; i++) {\n if (isPrime[i]) {\n if ((long)i * i > MAX_SUM) break; // 防止溢出\n for (int j = i * i; j <= MAX_SUM; j += i) {\n isPrime[j] = false;\n }\n }\n }\n }\n\n public static void main(String[] args) throws IOException {\n initPrime(); // 初始化纯粹数表\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int T = Integer.parseInt(br.readLine());\n StringBuilder sb = new StringBuilder();\n while (T-- > 0) {\n int n = Integer.parseInt(br.readLine());\n String[] aLine = br.readLine().split(" ");\n int[] a = new int[n];\n for (int i = 0; i < n; i++) {\n a[i] = Integer.parseInt(aLine[i]);\n }\n\n // 计算前缀和\n long[] prefix = new long[n + 1];\n for (int i = 1; i <= n; i++) {\n prefix[i] = prefix[i - 1] + a[i - 1];\n }\n\n // dp[i]：前i个元素的分割方案数\n long[] dp = new long[n + 1];\n dp[0] = 1; // 空序列方案数为1\n\n for (int i = 1; i <= n; i++) {\n for (int j = 0; j < i; j++) {\n long segSum = prefix[i] - prefix[j]; // 子段和\n if (segSum <= MAX_SUM && isPrime[(int)segSum]) {\n dp[i] = (dp[i] + dp[j]) % MOD; // 转移\n }\n }\n }\n\n sb.append(dp[n] % MOD).append("\n");\n }\n System.out.print(sb);\n }\n}\n