No.2568 Lexicographically Ordered Sequence of Sequences
タグ : / 解いたユーザー数 91
作問者 :
Magentor
/ テスター :
Kyo_s_s
kusirakusira
DeltaStruct
👑
けんぴん
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もしくは右上の雲マークをクリックしてアカウントを作成してください。