No.1353 Limited Sequence
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : 👑
PCTprobability
/ テスター :
KoD
blackyuki
タグ : / 解いたユーザー数 42
作問者 : 👑
PCTprobability
/ テスター :
KoD
blackyuki
問題文最終更新日: 2021-05-07 19:38:48
問題文
正整数 $N,L,R$ と正整数列 $A_1,A_2,...,A_N$ が与えられます。以下の条件を満たす正整数列 $B_1,B_2,...,B_K$ の数を $998244353$ で割った余りを求めてください。
- 全ての要素は $1$ 以上 $N$ 以下
- $L \le \displaystyle \sum_{i=1}^{K}B_i \le R$
- 正整数 $x,y(x \le y)$ に対して、$B_x$ から $B_y$ までの $y-x+1$ 要素全てが等しいならば、$y-x+1 \le A_{B_x}$
入力
$N \,\, L \,\, R$ $A_1 \,\, A_2 \,\, \ldots \,\, A_N$
- 入力は全て正整数である。
- $2 \le N \le 2000$
- $1 \le A_i \le 2000$
- $1 \le L \le R \le 2000$
出力
条件を満たす正整数列 $B_1,B_2,...,B_K$ の数を $998244353$ で割った余りを求めてください。
サンプル
サンプル1
入力
3 3 3
2 2 2
出力
3
あり得る数列としては、$1,2$ と $2,1$ と $3$ の $3$ 通りがあります。$1,1,1$ は条件 $3$ で、 $x=1,y=3$ とした時不適です。
サンプル2
入力
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
出力
468411411
$998244353$ で割った余りを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。