← 返回题目列表

AtCoder · xmascon21_c

C. 算我一个

中文机器翻译题面 查看原题

配点 : 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