問題一覧 > 通常問題

No.1353 Limited Sequence

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 44
作問者 : PCTprobability / テスター : KoD blackyuki
お気に入りにしたユーザー ProblemId : 5775 / 自分の提出
問題文最終更新日: 2021-05-07 19:38:48
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
灘中入試コンテストday2 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,L,R$ and a sequence of positive integers $A_1,A_2,...,A_N$. Find the number, modulo $998244353$, of sequences of positive integers $B_1,B_2,...,B_K$ that satisfy the following conditions.

  • All elements are between $1$ and $N$, inclusive.
  • $L \le \displaystyle \sum_{i=1}^{K}B_i \le R$
  • For positive integers $x,y(x \le y)$, if all $y-x+1$ elements from $B_x$ to $B_y$ are equal, then $y-x+1 \le A_{B_x}$.

Input

$N \,\, L \,\, R$
$A_1 \,\, A_2 \,\, \ldots \,\, A_N$



  • All inputs are positive integers.
  • $2 \le N \le 2000$
  • $1 \le A_i \le 2000$
  • $1 \le L \le R \le 2000$

Output

Output the number, modulo $998244353$, of sequences of positive integers $B_1,B_2,...,B_K$ that satisfy the conditions.

Sample

Sample 1
Input
3 3 3
2 2 2
Output
3

There are $3$ possible sequences: $1,2$, $2,1$, and $3$. The sequence $1,1,1$ is invalid because of condition $3$ with $x=1,y=3$.

Sample 2
Input
23 45 78
2 3 3 2 4 2 3 4 3 2 3 3 4 2 4 3 2 4 2 3 4 2 4
Output
468411411

Output the answer modulo $998244353$.

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