Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）
第二间隔AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given an integer $N$ and an integer sequence $D = (D_1, D_2, \ldots, D_{N-1})$ of length $N - 1$.
给定一个整数 $N$ 和一个长度为 $N - 1$ 的整数序列 $D = (D_1, D_2, \ldots, D_{N-1})$。AI (CI翻译)
Find the number, modulo $998244353$, of permutations $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ that satisfy the following condition.
求满足以下条件的 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 的数量，答案对 $998244353$ 取模。AI (CI翻译)
- For each
$1 \le i \le N - 1$, let$P_a$and$P_b$be the elements with the largest and the second largest values, respectively, among$(P_i, P_{i+1}, \ldots, P_N)$; then$|a - b| = D_i$.
- 对于每个
$1 \le i \le N - 1$，设$(P_i, P_{i+1}, \ldots, P_N)$中值最大和次大的元素分别为$P_a$和$P_b$，则满足$|a - b| = D_i$。
Constraints
约束条件
AI (CI翻译)$2 \le N \le 2 \times 10^5$$1 \le D_i \le N - i$- All input values are integers.
$2 \le N \le 2 \times 10^5$$1 \le D_i \le N - i$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
D_1 D_2 \ldots D_{N-1}N
D_1 D_2 \ldots D_{N-1}Output
输出格式
AI (CI翻译)Output the number, modulo $998244353$, of permutations satisfying the condition.
输出满足条件的排列数量，答案对 $998244353$ 取模。AI (CI翻译)
样例
Input #1
3
1 1
Output #1
4
For example, we can verify that $(2, 3, 1)$ satisfies the condition as follows.
- We have $(P_1, P_2, P_3) = (2, 3, 1)$. The largest value is $P_2$ and the second largest value is $P_1$, and $|2 - 1| = 1 = D_1$.
- We have $(P_2, P_3) = (3, 1)$. The largest value is $P_2$ and the second largest value is $P_3$, and $|2 - 3| = 1 = D_2$.
Four permutations satisfy the condition: $(1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1)$. Thus, output $4$.
Input #2
5
1 2 2 1
Output #2
0
Input #3
15
4 4 4 4 4 4 3 2 2 2 2 2 1 1
Output #3
70270200
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。