English · Original
Chinese · Translation
Formal · Original
In the platypus kingdom, there is a popular game throughout the kingdom–Hearthstone. Hearthstone consists of eight players in each game, and only one of them wins. Due to the difficulty of winning, many platypuses share their best moments of playing the game via live streams. Recently, a Bible "810975" spread.
"810975, why can't newcomers understand?!"
"810975, why are you the only one who doesn't understand?"
...
Recently, Zayin is reciting the Bible 810975 every day. He also continues to explain to his friends the specific meaning of 810975: On August 10, the Platypus King played 9 games and won 7 times, including a 5-game winning streak. But today, there comes a new platypus, Ziyin, who doesn't know the meaning of 810975. So Zayin excitedly explains to him. However, Ziyin has a question, "How many situations are there if I play $n$ games and win $m$ games, and the longest winning streak is $k$?"
If we use 1 to represent victory and 0 to represent defeat, any string consisting of 0 and 1 of length $n$ can represent a situation of an $n$-round game. Two situations are different if and only if the two 01 strings are different.
The first line contains three integers $n, m, k$ ($0 <= n, m, k <= 10^5$).
The only line contains an integer: the number of situations meeting the constraints. You should output the answer modulo $998244353$.
## Input
The first line contains three integers $n, m, k$ ($0 <= n, m, k <= 10^5$).
## Output
The only line contains an integer: the number of situations meeting the constraints. You should output the answer modulo $998244353$.
[samples]
我们有一条水平道路上的 $n$ 座塔。第 $i$ 座塔位于 $a_i$，其光强度为 $p_i$ 单位。然而，该塔的光强度效果随距离每增加 1 单位而减少 1 单位。这意味着对于位置 $x$，它从第 $i$ 座塔接收到的光强度为 $$ \max(0,p_i -|a_i - x|) $$ 对于位置 $j$，其接收到的光强度定义为所有塔提供的光强度中的最大值。给定同一条道路上 $m$ 个人的位置，请输出每个人接收到的光强度。
第一行包含两个整数 $n, m$ $(1 lt.eq n, m lt.eq 2 times 10^5)$，分别表示塔的数量和人的数量。
接下来 $n$ 行，每行包含两个整数 $a_i, p_i$ $(1 lt.eq a_i, p_i lt.eq 10^9)$，表示第 $i$ 座塔的位置和强度。
最后一行包含 $m$ 个整数 $b_1, b_2, dots.h, b_m$ $(1 lt.eq b_i lt.eq 10^9)$，表示每个人的_position_。
在第 $i$ 行输出第 $i$ 个人接收到的光强度。
## Input
第一行包含两个整数 $n, m$ $(1 lt.eq n, m lt.eq 2 times 10^5)$，表示塔的数量和人的数量。接下来 $n$ 行，每行包含两个整数 $a_i, p_i$ $(1 lt.eq a_i, p_i lt.eq 10^9)$，表示第 $i$ 座塔的位置和强度。最后一行包含 $m$ 个整数 $b_1, b_2, dots.h, b_m$ $(1 lt.eq b_i lt.eq 10^9)$，表示每个人的_position_。
## Output
在第 $i$ 行输出第 $i$ 个人接收到的光强度。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of towers and people.
Let $ T = \{(a_i, p_i) \mid i \in \{1, \dots, n\}\} $ be the set of towers, where $ a_i \in \mathbb{R} $ is the position and $ p_i \in \mathbb{Z}^+ $ is the intensity of the $ i $-th tower.
Let $ B = \{b_j \mid j \in \{1, \dots, m\}\} $ be the set of positions of people, where $ b_j \in \mathbb{R} $.
**Function**
For a tower at $ a_i $ with intensity $ p_i $, the light intensity at position $ x $ is:
$$
f_i(x) = \max(0, p_i - |a_i - x|)
$$
**Objective**
For each person at position $ b_j $, compute:
$$
L_j = \max_{i \in \{1, \dots, n\}} f_i(b_j) = \max_{i \in \{1, \dots, n\}} \max(0, p_i - |a_i - b_j|)
$$
**Constraints**
1. $ 1 \le n, m \le 2 \times 10^5 $
2. $ 1 \le a_i, p_i, b_j \le 10^9 $
API Response (JSON)
{
"problem": {
"name": "M. 810975",
"description": {
"content": "In the platypus kingdom, there is a popular game throughout the kingdom–Hearthstone. Hearthstone consists of eight players in each game, and only one of them wins. Due to the difficulty of winning, ma",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFM"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In the platypus kingdom, there is a popular game throughout the kingdom–Hearthstone. Hearthstone consists of eight players in each game, and only one of them wins. Due to the difficulty of winning, ma...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "我们有一条水平道路上的 $n$ 座塔。第 $i$ 座塔位于 $a_i$，其光强度为 $p_i$ 单位。然而，该塔的光强度效果随距离每增加 1 单位而减少 1 单位。这意味着对于位置 $x$，它从第 $i$ 座塔接收到的光强度为 $$ \\max(0,p_i -|a_i - x|) $$ 对于位置 $j$，其接收到的光强度定义为所有塔提供的光强度中的最大值。给定同一条道路上 $m$ 个人的位置，请输出...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of towers and people. \nLet $ T = \\{(a_i, p_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of towers, where $ a_i \\in \\mathbb{R} $ is th...",
"is_translate": false,
"language": "Formal"
}
]
}