/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
1, 2, \ldots, N の番号がついた人が円環状に並んでいます。
1 \leq i \leq N-1 を満たす人 i の右隣に人 i+1 がおり、人 N の右隣には人 1 がいます。
人 i ははじめ、a_i 個のボールを持っています。
以下の処理を一度だけ行います。
- それぞれの人が現在持っているボールのうちいくつかを選ぶ(0 個でもよい)
- その後、選んだボールを全て右隣の人に 同時に 渡す。
- 長さ N の数列を作る。数列の i 番目の要素は人 i が現在持っているボールの個数と等しい値である。
処理の結果できる数列としてありうるものの集合を S とします。 たとえば、a=(1,1,1) のとき S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \} です。
\sum_{x \in S} \prod_{i=1}^{N} x_i を 998244353 で割ったあまりを計算してください。
制約
- 与えられる入力は全て整数
- 3 \leq N \leq 10^5
- 0 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1} a_{2} \cdots a_{N}
出力
\sum_{x \in S} \prod_{i=1}^{N} x_i を 998244353 で割ったあまりを出力せよ。
入力例 1
3 1 1 1
出力例 1
1
- S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \} です。
- \sum_{x \in S} \prod_{i=1}^{N} x_i は 1 です。
入力例 2
3 2 1 1
出力例 2
6
入力例 3
20 5644 493 8410 8455 7843 9140 3812 2801 3725 6361 2307 1522 1177 844 654 6489 3875 3920 7832 5768
出力例 3
864609205
- 998244353 で割ったあまりを求めるのを忘れずに。
Score : 800 points
Problem Statement
N people called Person 1, 2, \ldots, N are standing in a circle.
For each 1 \leq i \leq N-1, Person i's neighbor to the right is Person i+1, and Person N's neighbor to the right is Person 1.
Person i initially has a_i balls.
They will do the following procedure just once.
- Each person chooses some (possibly zero) of the balls they have.
- Then, each person simultaneously hands the chosen balls to the neighbor to the right.
- Now, make a sequence of length N, where the i-th term is the number of balls Person i has at the moment.
Let S be the set of all sequences that can result from the procedure. For example, when a=(1,1,1), we have S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \}.
Compute \sum_{x \in S} \prod_{i=1}^{N} x_i, modulo 998244353.
Constraints
- All values in input are integers.
- 3 \leq N \leq 10^5
- 0 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
a_{1} a_{2} \cdots a_{N}
Output
Print \sum_{x \in S} \prod_{i=1}^{N} x_i, modulo 998244353.
Sample Input 1
3 1 1 1
Sample Output 1
1
- We have S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \}.
- \sum_{x \in S} \prod_{i=1}^{N} x_i is 1.
Sample Input 2
3 2 1 1
Sample Output 2
6
Sample Input 3
20 5644 493 8410 8455 7843 9140 3812 2801 3725 6361 2307 1522 1177 844 654 6489 3875 3920 7832 5768
Sample Output 3
864609205
- Be sure to compute it modulo 998244353.