33OJ
登录 注册

#P17531. [JAG 2026 Summer Camp #1] Professor JAG' s Language

[JAG 2026 Summer Camp #1] Professor JAG' s Language

题目描述

研究序列的 JAG 教授正在开发一种新的表达式语言。给定一个整数 NN,以及一个仅由 + 和 | 组成的字符串 O=O1O2⋯ON−1O=O_1O_2\cdots O_{N-1}。在本题中,元素依次为 a1,a2,…,aka_1,a_2,\ldots,a_k 的序列记为 [a1,a2,…,ak][a_1,a_2,\ldots,a_k]。

考虑以下表达式:

[1] O1 [2] O2 ⋯ ON−1 [N][1]\ O_1\ [2]\ O_2\ \cdots\ O_{N-1}\ [N]

这里,OiO_i 是输入字符串 OO 的第 ii 个字符,用作 [i][i] 和 [i+1][i+1] 之间的运算符。

由于没有规定运算符的优先级,我们考虑在不改变操作数和运算符顺序的前提下,为该表达式完整添加括号的所有方式。以这种方式得到的每个表达式称为一个合法表达式。

对于每个表达式 ZZ,设 S(Z)S(Z) 表示 ZZ 所代表的序列的集合。集合 S(Z)S(Z) 递归定义如下:

  • 若 ZZ 的形式为 [i],其中 1≤i≤N1\le i\le N,则 S(Z)S(Z) 中仅包含单元素序列 [i][i]。
  • 若 ZZ 的形式为 (X + Y),其中 XX、YY 分别是它的左右子表达式,则 S(Z)S(Z) 包含将 S(X)S(X) 中的一个序列与 S(Y)S(Y) 中的一个序列依次拼接所能得到的所有序列。例如,若 S(X)S(X) 包含 [1,3][1,3],而 S(Y)S(Y) 包含 [2,4][2,4],则 S(Z)S(Z) 包含 [1,3,2,4][1,3,2,4]。
  • 若 ZZ 的形式为 (X | Y),其中 XX、YY 分别是它的左右子表达式,则 S(Z)=S(X)∪S(Y)S(Z)=S(X)\cup S(Y)。

不同的合法表达式可能代表同一个序列。求至少能被一个合法表达式表示的不同序列的数量。由于答案可能很大,输出其对 998 244 353998\,244\,353 取模的结果。

输入格式

输入包含一组测试数据,格式如下:

N
O

第一行包含一个整数 NN(2≤N≤1062\le N\le 10^6)。第二行包含一个仅由 + 和 | 组成的字符串 OO(∣O∣=N−1|O|=N-1)。

输出格式

输出能够被表示的不同序列的数量,对 998 244 353998\,244\,353 取模。

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])))

以下四个不同的序列至少能被这些合法表达式中的一个表示:

  • [1,2][1,2]
  • [1,2,4][1,2,4]
  • [1,3,4][1,3,4]
  • [3,4][3,4]

因此,答案为 44。