题解

题目描述

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

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

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

解题思路

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

题目内容

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

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

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