問題一覧 > 通常問題

No.2568 Lexicographically Ordered Sequence of Sequences

レベル : / AI推定難易度 : 1175 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 91
作問者 : Magentor / テスター : deuteridayo 👑 AngrySadEight Kyo_s_s kusirakusira DeltaStruct 👑 loop0919 マベマス(mavemas_413) けんぴん aki
お気に入りにしたユーザー ProblemId : 9438 / 自分の提出
問題文最終更新日: 2023-11-30 18:46:36
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
第2回緑以下コンテスト (順位表) の他の問題:

Problem Statement

There are sequences of integer sequences $S_1,S_2,\dots,S_N$. $S_i=(S_{i,1},S_{i,2},\dots,S_{i,|S_i|})$ consists of all integer sequences of length $i$ whose elements are all between $1$ and $M$, inclusive, arranged in lexicographic order.

Formally, $S_i$ is a sequence of integer sequences satisfying the following conditions. (It can be proved that such a sequence is uniquely determined.)

  • For any integer sequence $T$ of length $i$ whose elements are all between $1$ and $M$, inclusive, there is exactly $1$ positive integer $j$ such that $S_{i,j}=T$.
  • If $j<k$, then $S_{i,j}$ is lexicographically smaller than $S_{i,k}$.

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ whose elements are all between $1$ and $M$, inclusive. Answer the $Q$ queries described below.

  • Query $i$: You are given integers $l_i,r_i$. Let $B_i = (A_{l_i},A_{l_i+1},\dots,A_{r_i})$, and let $K_i$ be the length of $B_i$. Output the value of the integer $j$ satisfying $S_{K_i,j}=B_i$, modulo $998244353$.
What is the lexicographic order of sequences?

A sequence $A=(A_1,A_2,\dots,A_{|A|})$ is lexicographically smaller than a sequence $B=(B_1,B_2,\dots,B_{|B|})$ if one of the following $2$ conditions holds. Here, $|A|,|B|$ denote the lengths of $A,B$, respectively.

  • $|A|<|B|$ and $(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|})$.
  • There exists an integer $1 \leq i \leq \min(|A|,|B|)$ such that both of the following $2$ conditions hold.
    • $(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})$
    • $A_i<B_i$

Constraints

  • All input values are integers.
  • $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$

Input

The input is given from Standard Input in the following format.

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

Output

Output the answers in $Q$ lines. The $i$-th line should contain the answer to query $i$.

Sample

Sample 1
Input
5 2 4
1 1 2 2 1
1 3
2 4
1 1
2 5
Output
2
4
1
7
  • In the $1$-st query, $B_1 = (1,1,2)$. Also, $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))$. Therefore, output $2$.
Sample 2
Input
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
Output
265251190
14039511
106
741215773
6798
0
17786
154
154
2

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