問題一覧 > 通常問題

No.2149 Vanitas Vanitatum

レベル : / AI推定難易度 : 2950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 28
作問者 : 👑 箱星 / テスター : hotman78
お気に入りにしたユーザー ProblemId : 8281 / 自分の提出
問題文最終更新日: 2022-12-02 20:15:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

Problem Statement

You are given a weakly increasing sequence of positive integers $A_1,A_2,\ldots,A_N$. Consider the following $2$ types of operations.

  • Choose $1$ index $i$ such that $A_i\ge 2$, and subtract $2$ from $A_i$. The sequence must be weakly increasing after the operation as well.
  • Choose $1$ index $i$ such that $A_i=A_{i+1}\ge 1$, and subtract $1$ from each of $A_i,A_{i+1}$. The sequence must be weakly increasing after the operation as well.

Operations are repeated until neither operation can be performed. Find the number of ways of performing the operations that make all of $A_1,A_2,\ldots,A_N$ equal to $0$, modulo $998244353$.

Constraints

  • $1\le N\le 1000$
  • $1\le A_1\le A_2\le\cdots\le A_N\le 1000$
  • All inputs are integers

Input

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the number of ways of performing the operations, modulo $998244353$.

Sample

Sample 1
Input
2
3 3
Output
3

There are the following $3$ ways.

  • $(3,3) \to (2,2) \to (1,1) \to (0,0)$
  • $(3,3) \to (2,2) \to (0,2) \to (0,0)$
  • $(3,3) \to (1,3) \to (1,1) \to (0,0)$
Sample 2
Input
5
1 3 5 7 9
Output
0

It is impossible to make all of them $0$.

Sample 3
Input
4
1000 1000 1000 1000
Output
55019937

Find the answer modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。