← 返回题目列表

AtCoder · arc193_b

B. 轮子坏了

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

分数: 800 点

问题陈述

给你一个正整数 N 和长度-N 字符串 s_0s_1\ldots s_{N-1} 仅包含 0 和 1.

考虑一个简单的无向图 G 与 (N+1) 顶点编号 0, 1, 2, \ldots, N,以及以下边:

  • 对于每个 i = 0, 1, \ldots, N-1,顶点之间有一条无向边 i 和 (i+1)\bmod N.
  • 对于每个 i = 0, 1, \ldots, N-1,顶点之间有一条无向边 i 和 N 当且仅当 s_i = 1.
  • 没有其他边。

此外,创建一个有向图 G' 通过为每个边缘分配一个方向 G。也就是说,对于每个无向边 \lbrace u, v \rbrace in G,将其替换为有向边 (u, v) 来自 u to v 或有向边 (v, u) 来自 v to u.

对于每个 i = 0, 1, \ldots, N,让 d_i 是顶点的入度 i in G'。打印数字,模数 998244353,具有不同的序列 可以获得 (d_0, d_1, \ldots, d_N) 。

约束

  • 3 \leq N \leq 10^6
  • N 是一个整数。
  • 每个 s_i is 0 or 1.

输入

输入由标准输入按以下格式给出:

N
s_0s_1\ldots s_{N-1}

输出

打印答案。


样本输入 1

3
010

示例输出 1

14

G 有四个无向边: \lbrace 0, 1 \rbrace, \lbrace 0, 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace。 例如,如果我们将方向分配给每条边 获得 0 \to 1, 2 \to 0, 2 \to 1, 1 \to 3,那么 (d_0, d_1, d_2, d_3) = (1, 2, 0, 1) 。

可能的序列 (d_0, d_1, d_2, d_3) 是 (0, 1, 2, 1), (0, 2, 1, 1), (0, 2, 2, 0), (0, 3, 1, 0), (1, 0, 2, 1), (1, 1, 1, 1), (1, 1, 2, 0), (1, 2, 0, 1), (1, 2, 1, 0), (1, 3, 0, 0), (2, 0, 1, 1), (2, 1, 0, 1), (2, 1, 1, 0), (2, 2, 0, 0),总共 14.


示例输入 2

20
00001100111010100101

示例输出 2

261339902