問題一覧 > 通常問題

No.2568 列辞書順列列

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

問題文

整数列の列 S1,S2,…,SNS_1,S_2,\dots,S_N があります。Si=(Si,1,Si,2,…,Si,∣Si∣)S_i=(S_{i,1},S_{i,2},\dots,S_{i,|S_i|}) には長さ ii ですべての要素が 11 以上 MM 以下である整数列全てが辞書順に並んでいます。

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

  • TT を長さ ii ですべての要素が 11 以上 MM 以下である整数列とするとき、Si,j=TS_{i,j}=T となる正整数 jj はちょうど 11 つである。
  • j<kj<k であるとき、Si,jS_{i,j} は Si,kS_{i,k} よりも辞書順で小さい。

全ての要素が 11 以上 MM 以下である整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) が与えられるので、以下で説明される QQ 個のクエリに答えてください。

  • クエリ ii : 整数 li,ril_i,r_i が与えられる。Bi=(Ali,Ali+1,…,Ari)B_i = (A_{l_i},A_{l_i+1},\dots,A_{r_i}) として、BiB_i の長さを KiK_i としたとき、SKi,j=BiS_{K_i,j}=B_i を満たす整数 jj の値を 998244353998244353 で割った余りを出力する。
数列の辞書順とは？

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

  • ∣A∣<∣B∣|A|<|B| かつ (A1,A2,…,A∣A∣)=(B1,B2,…,B∣A∣)(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|}) である。
  • ある整数 1≤i≤min⁡(∣A∣,∣B∣)1 \leq i \leq \min(|A|,|B|) が存在して、以下の 22 つが成り立つ。
    • (A1,A2,…,Ai−1)=(B1,B2,…,Bi−1)(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})
    • Ai<BiA_i<B_i

制約

  • 入力は全て整数である
  • 1≤N,M≤2×1051 \leq N,M \leq 2 \times 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1≤Ai≤M1 \leq A_i \leq M
  • 1≤li≤ri≤N1 \leq l_i \leq r_i \leq N

入力

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

N M QN\ M\ Q
A1 A2 … ANA_1\ A_2\ \dots\ A_N
l1 r1l_1\ r_1
l2 r2l_2\ r_2
⋮\vdots
lQ rQl_Q\ r_Q

出力

答えを QQ 行に出力せよ。ii 行目には、クエリ ii の答えを出力せよ。

サンプル

サンプル1
入力
5 2 4
1 1 2 2 1
1 3
2 4
1 1
2 5
出力
2
4
1
7
  • 11 番目のクエリにおいて、B1=(1,1,2)B_1 = (1,1,2) です。また、S3=((1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,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)) となります。よって 22 を出力します。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。