English · Original
Chinese · Translation
Formal · Original
In "_The Man in the High Castle_" world, there are $m$ different film endings.
Abendsen owns a storage and a shelf. At first, he has $n$ ordered films on the shelf. In the $i$\-th month he will do:
1. Empty the storage.
2. Put $k_i \cdot m$ films into the storage, $k_i$ films for each ending.
3. He will think about a question: if he puts all the films from the shelf into the storage, then randomly picks $n$ films (from all the films in the storage) and rearranges them on the shelf, what is the probability that sequence of endings in $[l_i, r_i]$ on the shelf will not be changed? Notice, he just thinks about this question, so the shelf will not actually be changed.
Answer all Abendsen's questions.
Let the probability be fraction $P_i$. Let's say that the total number of ways to take $n$ films from the storage for $i$\-th month is $A_i$, so $P_i \cdot A_i$ is always an integer. Print for each month $P_i \cdot A_i \pmod {998244353}$.
$998244353$ is a prime number and it is equal to $119 \cdot 2^{23} + 1$.
It is guaranteed that there will be only no more than $100$ different $k$ values.
## Input
The first line contains three integers $n$, $m$, and $q$ ($1 \le n, m, q \le 10^5$, $n+q\leq 10^5$) — the number of films on the shelf initially, the number of endings, and the number of months.
The second line contains $n$ integers $e_1, e_2, \ldots, e_n$ ($1\leq e_i\leq m$) — the ending of the $i$\-th film on the shelf.
Each of the next $q$ lines contains three integers $l_i$, $r_i$, and $k_i$ ($1 \le l_i \le r_i \le n, 0 \le k_i \le 10^5$) — the $i$\-th query.
It is guaranteed that there will be only no more than $100$ different $k$ values.
## Output
Print the answer for each question in a separate line.
[samples]
## Note
In the first sample in the second query, after adding $2 \cdot m$ films into the storage, the storage will look like this: ${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$.
There are $26730$ total ways of choosing the films so that $e_l, e_{l+1}, \ldots, e_r$ will not be changed, for example, $[1, 2, 3, 2, 2]$ and $[1, 2, 3, 4, 3]$ are such ways.
There are $2162160$ total ways of choosing the films, so you're asked to print $(\frac{26730}{2162160} \cdot 2162160) \mod 998244353 = 26730$.
在《高堡奇人》的世界中，有 $m$ 种不同的电影结局。
Abendsen 拥有一个存储空间和一个书架。最初，他书架上有 $n$ 部有序的电影。在第 $i$ 个月，他会执行：
回答 Abendsen 的所有问题。
设概率为分数 $P_i$。设第 $i$ 个月从存储中选取 $n$ 部电影的总方式数为 $A_i$，则 $P_i dot.op A_i$ 总是整数。请对每个月输出 $P_i dot.op A_i pmod 998244353$。
$998244353$ 是一个质数，等于 $119 dot.op 2^(23) + 1$。
保证不同的 $k$ 值不超过 $100$ 个。
第一行包含三个整数 $n$，$m$ 和 $q$（$1 lt.eq n, m, q lt.eq 10^5$，$n + q lt.eq 10^5$）——初始书架上的电影数量、结局数量和月份数。
第二行包含 $n$ 个整数 $e_1, e_2, dots.h, e_n$（$1 lt.eq e_i lt.eq m$）——书架上第 $i$ 部电影的结局。
接下来的 $q$ 行每行包含三个整数 $l_i$，$r_i$ 和 $k_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$0 lt.eq k_i lt.eq 10^5$）——第 $i$ 个查询。
保证不同的 $k$ 值不超过 $100$ 个。
请对每个查询的答案单独输出一行。
在第一个样例的第二个查询中，向存储中添加 $2 dot.op m$ 部电影后，存储将变为：${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$。
共有 $26730$ 种选择电影的方式，使得 $e_l, e_(l + 1), dots.h, e_r$ 保持不变，例如 $[ 1, 2, 3, 2, 2 ]$ 和 $[ 1, 2, 3, 4, 3 ]$ 就是这样的方式。
共有 $2162160$ 种选择电影的总方式，因此你需要输出 $(frac(26730, 2162160) dot.op 2162160) mod 998244353 = 26730$。
## Input
第一行包含三个整数 $n$，$m$ 和 $q$（$1 lt.eq n, m, q lt.eq 10^5$，$n + q lt.eq 10^5$）——初始书架上的电影数量、结局数量和月份数。第二行包含 $n$ 个整数 $e_1, e_2, dots.h, e_n$（$1 lt.eq e_i lt.eq m$）——书架上第 $i$ 部电影的结局。接下来的 $q$ 行每行包含三个整数 $l_i$，$r_i$ 和 $k_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$0 lt.eq k_i lt.eq 10^5$）——第 $i$ 个查询。保证不同的 $k$ 值不超过 $100$ 个。
## Output
请对每个查询的答案单独输出一行。
[samples]
## Note
在第一个样例的第二个查询中，向存储中添加 $2 dot.op m$ 部电影后，存储将变为：${1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4}$。共有 $26730$ 种选择电影的方式，使得 $e_l, e_(l + 1), dots.h, e_r$ 保持不变，例如 $[ 1, 2, 3, 2, 2 ]$ 和 $[ 1, 2, 3, 4, 3 ]$ 就是这样的方式。共有 $2162160$ 种选择电影的总方式，因此你需要输出 $(frac(26730, 2162160) dot.op 2162160) mod 998244353 = 26730$。
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ with $ 1 \le n, m, q \le 10^5 $ and $ n + q \le 10^5 $.
Let $ E = (e_1, e_2, \dots, e_n) $ be the initial sequence of film endings, where $ e_i \in \{1, 2, \dots, m\} $.
For each query $ i \in \{1, \dots, q\} $, let $ (l_i, r_i, k_i) $ denote:
- $ l_i, r_i \in \mathbb{Z} $: indices defining a contiguous subsequence $ E[l_i:r_i] $ to remain unchanged.
- $ k_i \in \mathbb{Z}_{\ge 0} $: number of **additional** films of **each** ending added to storage (i.e., storage gains $ k_i $ copies of each of the $ m $ endings).
Let $ S_i $ be the set of all possible sequences of $ n $ films chosen from storage (after adding $ k_i $ copies per ending) such that the subsequence from index $ l_i $ to $ r_i $ matches $ E[l_i:r_i] $.
Let $ A_i $ be the total number of ways to choose any sequence of $ n $ films from storage (after adding $ k_i $ copies per ending).
Let $ P_i = \frac{|S_i|}{A_i} $ be the probability that a random sequence matches $ E[l_i:r_i] $ on positions $ l_i $ to $ r_i $.
**Constraints**
1. $ 1 \le l_i < r_i \le n $
2. $ 0 \le k_i \le 10^5 $
3. There are at most 100 distinct values of $ k_i $ across all queries.
4. Storage initially contains no films; after query $ i $, storage has $ k_i $ copies of each of the $ m $ endings (i.e., total $ m \cdot k_i $ films added).
5. The shelf must be filled with exactly $ n $ films, each chosen from storage (with unlimited supply per ending after addition).
6. The subsequence $ E[l_i:r_i] $ must be preserved exactly in positions $ l_i $ to $ r_i $.
**Objective**
For each query $ i $, compute:
$$
P_i \cdot A_i \mod 998244353 = |S_i| \mod 998244353
$$
That is, output the number of valid sequences $ \in S_i $ modulo $ 998244353 $.
API Response (JSON)
{
"problem": {
"name": "H. The Films",
"description": {
"content": "In \"_The Man in the High Castle_\" world, there are $m$ different film endings. Abendsen owns a storage and a shelf. At first, he has $n$ ordered films on the shelf. In the $i$\\-th month he will do: ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1017H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In \"_The Man in the High Castle_\" world, there are $m$ different film endings.\n\nAbendsen owns a storage and a shelf. At first, he has $n$ ordered films on the shelf. In the $i$\\-th month he will do:\n\n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在《高堡奇人》的世界中，有 $m$ 种不同的电影结局。\n\nAbendsen 拥有一个存储空间和一个书架。最初，他书架上有 $n$ 部有序的电影。在第 $i$ 个月，他会执行：\n\n回答 Abendsen 的所有问题。\n\n设概率为分数 $P_i$。设第 $i$ 个月从存储中选取 $n$ 部电影的总方式数为 $A_i$，则 $P_i dot.op A_i$ 总是整数。请对每个月输出 $P_i dot.o...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 1 \\le n, m, q \\le 10^5 $ and $ n + q \\le 10^5 $. \nLet $ E = (e_1, e_2, \\dots, e_n) $ be the initial sequence of film endings, where $ e_i \\in...",
"is_translate": false,
"language": "Formal"
}
]
}