問題一覧 > 通常問題

No.1353 Limited Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : PCTprobabilityPCTprobability / テスター : KoDKoD blackyukiblackyuki
2 ProblemId : 5775 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。