/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
正整数 N と、0 と 1 のみからなる長さ N の文字列 s_0s_1\ldots s_{N-1} が与えられます。
0, 1, 2, \ldots, N と番号づけられた (N+1) 個の頂点と、下記の辺からなる単純無向グラフ G を考えます。
- 各 i = 0, 1, \ldots, N-1 について、頂点 i と頂点 (i+1)\bmod N を結ぶ無向辺がある。
- 各 i = 0, 1, \ldots, N-1 について、s_i =
1のとき、かつ、そのときに限り、頂点 i と頂点 N を結ぶ無向辺がある。 - 上記の他に辺はない。
さらに、G の各辺を任意に向きづけして有向グラフ G' を作ります。すなわち、G の各無向辺 \lbrace u, v \rbrace を、 u から v への有向辺 (u, v) と v から u への有向辺 (v, u) のどちらか一方で置き換えます。
各 i = 0, 1, \ldots, N について、G' における頂点 i の入次数を d_i とおくとき、 得られる数列 (d_0, d_1, \ldots, d_N) としてありえるものの個数を 998244353 で割った余りを出力してください。
制約
- 3 \leq N \leq 10^6
- N は整数
- s_i は
0または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 の 4 本の無向辺を持ちます。 例えば、それぞれの辺を 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
Score : 800 points
Problem Statement
You are given a positive integer N and a length-N string s_0s_1\ldots s_{N-1} consisting only of 0 and 1.
Consider a simple undirected graph G with (N+1) vertices numbered 0, 1, 2, \ldots, N, and the following edges:
- For each i = 0, 1, \ldots, N-1, there is an undirected edge between vertices i and (i+1)\bmod N.
- For each i = 0, 1, \ldots, N-1, there is an undirected edge between vertices i and N if and only if s_i =
1. - There are no other edges.
Furthermore, create a directed graph G' by assigning a direction to each edge of G. That is, for each undirected edge \lbrace u, v \rbrace in G, replace it with either a directed edge (u, v) from u to v or a directed edge (v, u) from v to u.
For each i = 0, 1, \ldots, N, let d_i be the in-degree of vertex i in G'. Print the number, modulo 998244353, of distinct sequences (d_0, d_1, \ldots, d_N) that can be obtained.
Constraints
- 3 \leq N \leq 10^6
- N is an integer.
- Each s_i is
0or1.
Input
The input is given from Standard Input in the following format:
N
s_0s_1\ldots s_{N-1}
Output
Print the answer.
Sample Input 1
3 010
Sample Output 1
14
G has four undirected edges: \lbrace 0, 1 \rbrace, \lbrace 0, 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace. For example, if we assign directions to each edge as 0 \to 1, 2 \to 0, 2 \to 1, 1 \to 3, then (d_0, d_1, d_2, d_3) = (1, 2, 0, 1) is obtained.
The possible sequences (d_0, d_1, d_2, d_3) are (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), for a total of 14.
Sample Input 2
20 00001100111010100101
Sample Output 2
261339902