单点时限: 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 取模的结果。
3 10?
499122181
5 ?????
124780551
样例1解释：当 ? 处填 0 时，后缀自动机有五个结点，填 1 时有四个结点，所以答案为 92。
对于所有数据，满足 1≤n≤36。
本题共 20 组数据，对于第 i 组数据有 n=min(36,18+i)。
1 人解决，9 人已尝试。
1 份提交通过，共有 25 份提交。
9.9 EMB 奖励。
创建: 3 年，11 月前.
修改: 3 年，11 月前.
最后提交: 1 年，3 月前.
来源: N/A