Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
1 以上 N 以下の整数からなる整数列 B のうち、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを出力してください。
- 1 \le i \le N を満たす整数 i に対し、B の中に i はちょうど A_i 個存在する。
- 1 \le i \le |B|-1 を満たす整数 i に対し、|B_i - B_{i+1}|=1 が成り立つ。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 2 3 1
出力例 1
6
B としてあり得るものは、以下の 6 通りがあります。
- (1,2,1,2,3,2)
- (1,2,3,2,1,2)
- (2,1,2,1,2,3)
- (2,1,2,3,2,1)
- (2,3,2,1,2,1)
- (3,2,1,2,1,2)
よって、解は 6 です。
入力例 2
1 200000
出力例 2
0
条件を満たす B が存在しないこともあります。
入力例 3
6 12100 31602 41387 41498 31863 12250
出力例 3
750337372
Score : 800 points
Problem Statement
You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).
How many integer sequences B consisting of integers between 1 and N (inclusive) satisfy all of the following conditions? Print the count modulo 998244353.
- For each integer i such that 1 \le i \le N, there are exactly A_i occurrences of i in B.
- For each integer i such that 1 \le i \le |B|-1, it holds that |B_i - B_{i+1}|=1.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 2 3 1
Sample Output 1
6
B can be the following six sequences.
- (1,2,1,2,3,2)
- (1,2,3,2,1,2)
- (2,1,2,1,2,3)
- (2,1,2,3,2,1)
- (2,3,2,1,2,1)
- (3,2,1,2,1,2)
Thus, the answer is 6.
Sample Input 2
1 200000
Sample Output 2
0
There may be no sequence that satisfies the conditions.
Sample Input 3
6 12100 31602 41387 41498 31863 12250
Sample Output 3
750337372