1000ms

Difficulty: 6

所属公司 : 美团

时间 :2025年5月31日-算法岗

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

题解

题目描述

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

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

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

解题思路

题目内容

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

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

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