配点 : 100 点
由于有传说说斑马的条纹每一代会增加一个,请计算其变化的过程。
問題文
文字 0, 1, ? 组成的长度 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. S 被给出。字符串的 N + 1 個組 (t_0, t_1, \ldots, t_N) 的数量除以 998244353 的余数:
- t_0 是空字符串。 可以通过插入到
- 各 i = 0, 1, \ldots, N - 1 ,
定义t_{i+1} 是t_i 至
该值是
0或 至少1该值应乘以 1 个任意位置得到的字符串。 通过替换为 - t_N 是S 出现在
?分别 定义0或 至少1得到的字符串。
制約
- 1 \le N \le 250\,000.
- S 是
您也可以写
0,1,?组成的长度 N 的字符串.
部分点
- N \le 5\,000 的数据集,10 点。 如果所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 90 点。 如果所有满足
入力
输入是按以下格式从标准输入给出的。
N S
出力
的数量为 998244353 后的余数。 对于
入力例 1
3 01?
出力例 1
8
满足条件的集合 (t_0, t_1, t_2, t_3) 如下 8 :
- t_0 是空字符串,t_1 是
在
0,t_2 是 在00,t_3 是 在010. - t_0 是空字符串,t_1 是
在
0,t_2 是 在01,t_3 是 在010. - t_0 是空字符串,t_1 是
在
0,t_2 是 在01,t_3 是 在011. - t_0 是空字符串,t_1 是
在
0,t_2 是 在10,t_3 是 在010. - t_0 是空字符串,t_1 是
在
1,t_2 是 在01,t_3 是 在010. - t_0 是空字符串,t_1 是
在
1,t_2 是 在01,t_3 是 在011. - t_0 是空字符串,t_1 是
在
1,t_2 是 在10,t_3 是 在010. - t_0 是空字符串,t_1 是
在
1,t_2 是 在11,t_3 是 在011.
入力例 2
9 0??001011
出力例 2
32400
入力例 3
40 1111111111111111111100000000000000000000
出力例 3
88808106