201244: [AtCoder]ARC124 E - Pass to Next

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

有 $n$ 个人站成一个圈,分别编号为 $1\sim n$,编号为 $i$ 的人右边为编号为 $i\bmod n+1$ 的人。初始第 $i$ 个人有 $a_i$ 个球。 接下来,他们会选择一些自己手中的球(可以不选),接着**所有人同时**将选中的球传给右边的人(这意味着别人传过来的球是不能继续往下传的)。我们令传球后第 $i$ 个人拥有的球数为 $b_i$。 令 $S$ 为所有可能的序列 $b$ 构成的集合。例如,$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}^nx_i$$ 输出答案模 $998244353$ 的值。

加入题单

上一题 下一题 算法标签: