4253. 力脑

单点时限: 3.0 sec

内存限制: 512 MB

有一长度为 $n$ 的仅由 $0$ 和 $1$ 构成的字符串 $S$,某些位置的字符已经给定,其他位置的字符等概率取 $0$ 或 $1$,求 $S$ 的后缀自动机的结点数量的期望。

答案对 $998244353$ 取模。

关于后缀自动机的定义:请点这里

简单来说,如果我们定义集合 $endpos(t)$ 表示一个字符串 $t$ 在 $S$ 中每一次作为连续子串出现的结束位置,$S$ 的后缀自动机结点数量等于不同的 $endpos$ 个数。这里空集合即初始状态也算作结点。

输入格式

第一行:一个整数 $n$,表示字符串长度。

第二行:一个长度为 $n$ 的字符串,包含 $0,1,?$ 三种字符,分别表示 $S$ 对应位置必定为 $0$,必定为 $1$,或随机取。

输出格式

输出一行一个整数:表示答案对 $998244353$ 取模的结果。

样例

Input
3
10?
Output
499122181
Input
5
?????
Output
124780551

提示

样例$1$解释:当 $?$ 处填 $0$ 时,后缀自动机有五个结点,填 $1$ 时有四个结点,所以答案为 $\frac{9}{2}$。

对于所有数据,满足 $1 \le n \le 36$。

本题共 $20$ 组数据,对于第 $i$ 组数据有 $n=\min(36,18+i)$。

0 人解决,7 人已尝试。

0 份提交通过,共有 20 份提交。

9.9 EMB 奖励。

创建: 6 月前.

修改: 6 月前.

最后提交: 5 月,3 周前.

来源: N/A

题目标签