問題一覧 > 通常問題

No.2568 列辞書順列列

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : MagentorMagentor / テスター : deuteridayodeuteridayo 👑 AngrySadEightAngrySadEight Kyo_s_sKyo_s_s kusirakusirakusirakusira DeltaStructDeltaStruct loop0919loop0919 マベマス（mavemas_413）マベマス（mavemas_413） けんぴんけんぴん akiaki
2 ProblemId : 9438 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:46:36

問題文

整数列の列 $S_1,S_2,\dots,S_N$ があります。$S_i=(S_{i,1},S_{i,2},\dots,S_{i,|S_i|})$ には長さ $i$ ですべての要素が $1$ 以上 $M$ 以下である整数列全てが辞書順に並んでいます。

厳密には、$S_i$ は以下の条件を満たす整数列の列です。(このようなものは一意に定まることが証明できます。)

  • $T$ を長さ $i$ ですべての要素が $1$ 以上 $M$ 以下である整数列とするとき、$S_{i,j}=T$ となる正整数 $j$ はちょうど $1$ つである。
  • $j<k$ であるとき、$S_{i,j}$ は $S_{i,k}$ よりも辞書順で小さい。

全ての要素が $1$ 以上 $M$ 以下である整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられるので、以下で説明される $Q$ 個のクエリに答えてください。

  • クエリ $i$ : 整数 $l_i,r_i$ が与えられる。$B_i = (A_{l_i},A_{l_i+1},\dots,A_{r_i})$ として、$B_i$ の長さを $K_i$ としたとき、$S_{K_i,j}=B_i$ を満たす整数 $j$ の値を $998244353$ で割った余りを出力する。
数列の辞書順とは？

数列 $A=(A_1,A_2,\dots,A_{|A|})$ が数列 $B=(B_1,B_2,\dots,B_{|B|})$ よりも辞書順で小さいとは、以下の $2$ つのうちどちらかが成り立つことを言います。ここで、$|A|,|B|$ はそれぞれ $A,B$ の長さを表します。

  • $|A|<|B|$ かつ $(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|})$ である。
  • ある整数 $1 \leq i \leq \min(|A|,|B|)$ が存在して、以下の $2$ つが成り立つ。
    • $(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})$
    • $A_i<B_i$

制約

  • 入力は全て整数である
  • $1 \leq N,M \leq 2 \times 10^5$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i \leq M$
  • $1 \leq l_i \leq r_i \leq N$

入力

入力は以下の形式で標準入力から与えられる。

$N\ M\ Q$
$A_1\ A_2\ \dots\ A_N$
$l_1\ r_1$
$l_2\ r_2$
$\vdots$
$l_Q\ r_Q$

出力

答えを $Q$ 行に出力せよ。$i$ 行目には、クエリ $i$ の答えを出力せよ。

サンプル

サンプル1
入力
5 2 4
1 1 2 2 1
1 3
2 4
1 1
2 5
出力
2
4
1
7
  • $1$ 番目のクエリにおいて、$B_1 = (1,1,2)$ です。また、$S_3 = ((1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2))$ となります。よって $2$ を出力します。
サンプル2
入力
15 13 10
1 9 2 4 2 3 12 11 8 5 1 5 2 12 11
1 15
6 12
1 3
7 14
4 7
5 13
2 5
14 15
7 8
3 3
出力
265251190
14039511
106
741215773
6798
0
17786
154
154
2

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