#P17531. [JAG 2026 Summer Camp #1] Professor JAG' s Language
[JAG 2026 Summer Camp #1] Professor JAG' s Language
题目描述
研究序列的 JAG 教授正在开发一种新的表达式语言。给定一个整数 ,以及一个仅由 + 和 | 组成的字符串 。在本题中,元素依次为 的序列记为 。
考虑以下表达式:
这里, 是输入字符串 的第 个字符,用作 和 之间的运算符。
由于没有规定运算符的优先级,我们考虑在不改变操作数和运算符顺序的前提下,为该表达式完整添加括号的所有方式。以这种方式得到的每个表达式称为一个合法表达式。
对于每个表达式 ,设 表示 所代表的序列的集合。集合 递归定义如下:
- 若 的形式为
[i],其中 ,则 中仅包含单元素序列 。 - 若 的形式为
(X + Y),其中 、 分别是它的左右子表达式,则 包含将 中的一个序列与 中的一个序列依次拼接所能得到的所有序列。例如,若 包含 ,而 包含 ,则 包含 。 - 若 的形式为
(X | Y),其中 、 分别是它的左右子表达式,则 。
不同的合法表达式可能代表同一个序列。求至少能被一个合法表达式表示的不同序列的数量。由于答案可能很大,输出其对 取模的结果。
输入格式
输入包含一组测试数据,格式如下:
N
O
第一行包含一个整数 ()。第二行包含一个仅由 + 和 | 组成的字符串 ()。
输出格式
输出能够被表示的不同序列的数量,对 取模。
4
+|+
4
7
||+|||
17
17
+|||+|+++||||+|+
1774
提示
在第一个样例中,表达式为 [1]+[2]|[3]+[4]。
通过添加括号,可以得到以下五个合法表达式:
((([1]+[2])|[3])+[4])(([1]+[2])|([3]+[4]))(([1]+([2]|[3]))+[4])([1]+(([2]|[3])+[4]))([1]+([2]|([3]+[4])))
以下四个不同的序列至少能被这些合法表达式中的一个表示:
因此,答案为 。