首页 > 试题广场 >

小苯的合序并列

[编程题]小苯的合序并列
  • 热度指数：251 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯有一个长度为 n 的序列 a，但小苯现在只对合数感兴趣，因此小苯希望 a 中所有的元素都是合数。
为此，小苯可以做如下的操作任意次：

\bullet 选择一对相邻的数字，将他们合并成一个数，结果为两者的积。
（形式化的：选择 i\ (1 \leq i < n)，将 a_i 和 a_{i+1} 合并为一个数字，结果是 a_i \times a_{i+1}。

小苯想知道，如果要满足他的条件（即所有元素都是合数），则在他操作完后，a 有多少种可能的形态，请你帮他算一算吧。
（小苯认为两个序列 a,b 的最终形态不同，当且仅当两个序列 a,b 的长度不同、或者长度相同且存在 i 使得 a_i \ne b_i。）

输入描述:
本题有多组测试数据。
输入的第一行包含一个正整数 T\ (1 \leq T \leq 100)，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行一个正整数 n\ (1 \leq n \leq 2 \times 10^5)，表示序列 a 的长度。
第二行 n 个正整数 a_i\ (1 \leq a_i \leq 10^6)，表示序列 a。
（保证所有测试数据中，n 的总和不超过 2 \times 10^5。）


输出描述:
对于每组测试数据：
在单独的一行输出一个整数，表示最终符合条件的 a 的可能结果。特别的，如果无论如何操作都无法满足小苯的条件则输出 0。
（由于结果可能很大，因此你只需要输出结果对 998244353 取模的值即可。）
示例1

输入

1
5
2 4 3 4 1

输出

3
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

动态规划 数论 阿里云
难度：
0条回答 234浏览

热门推荐

相关试题

小苯的合序并列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号