310360: CF1821F. Timber
Description
There is a beautiful alley with trees in front of a shopping mall. Unfortunately, it has to go to make space for the parking lot.
The trees on the alley all grow in a single line. There are $n$ spots for trees, index $0$ is the shopping mall, index $n+1$ is the road and indices from $1$ to $n$ are the spots for trees. Some of them are taken — there grow trees of the same height $k$. No more than one tree grows in each spot.
When you chop down a tree in the spot $x$, you can make it fall either left or right. If it falls to the left, it takes up spots from $x-k$ to $x$, inclusive. If it falls to the right, it takes up spots from $x$ to $x+k$, inclusive.
Let $m$ trees on the alley grow in some spots $x_1, x_2, \dots, x_m$. Let an alley be called unfortunate if all $m$ trees can be chopped down in such a way that:
- no tree falls on the shopping mall or the road;
- each spot is taken up by no more than one fallen tree.
Calculate the number of different unfortunate alleys with $m$ trees of height $k$. Two alleys are considered different if there is a spot $y$ such that a tree grows in $y$ on the first alley and doesn't grow in $y$ on the second alley.
Output the number modulo $998\,244\,353$.
InputThe only line contains three integers $n, m$ and $k$ ($1 \le m, k \le n \le 3 \cdot 10^5$) — the number of spots for the trees, the number of trees and the height of each tree.
OutputPrint a single integer — the number of different unfortunate alleys with $m$ trees of height $k$, modulo $998\,244\,353$.
ExamplesInput6 1 4Output
4Input
5 2 2Output
0Input
6 2 2Output
4Input
15 3 2Output
311
Input
题意翻译
在 $[1, n]$ 的区间里放 $m$ 棵树，每棵树的高度为 $k$。求有多少种放置树的方法，满足： 1. 每个树都在整点上，且每个点最多只能放一棵树。 2. 存在一种砍倒树的方案，使得树倒了之后不会越界，也不会有某个点被超过一棵树占据。你可以自由选择树向左倒（也就是占据区间 $[x - k, x]$）或者向右倒（也就是占据区间 $[x, x + k]$）。 $1\leq n, m, k\leq 3\times 10 ^ 5$。Output
一个购物中心前有一条美丽的树木小巷，树木都种在同一直线上。小巷上有n个位置可以种树，编号从0到n+1，其中0代表购物中心，n+1代表道路，1到n是种树的位置。有些位置已经种上了高度相同的树k，每个位置最多有一棵树。砍倒位置x的树时，可以选择让树向左或向右倒下。如果向左倒，它会占据从x-k到x（包括x）的位置。如果向右倒，它会占据从x到x+k（包括x）的位置。给定m棵树在小巷上的位置x_1, x_2, ..., x_m。如果所有m棵树都可以被砍倒，且不倒在购物中心或道路上，并且每个位置最多只有一棵倒下的树，则称这样的小巷为“不幸的”。计算有多少种不同的“不幸的”小巷，其中种有m棵高度为k的树。如果存在一个位置y，在第一条小巷上有树，而在第二条小巷上没有树，则认为这两条小巷是不同的。输出结果对998,244,353取模。
输入数据格式：
输入只有一行，包含三个整数n, m和k（1 ≤ m, k ≤ n ≤ 3 × 10^5）——树木的位置数、树木的数量和每棵树的高度。
输出数据格式：
输出一个整数——有多少种不同的“不幸的”小巷，其中种有m棵高度为k的树，结果对998,244,353取模。题目大意： 一个购物中心前有一条美丽的树木小巷，树木都种在同一直线上。小巷上有n个位置可以种树，编号从0到n+1，其中0代表购物中心，n+1代表道路，1到n是种树的位置。有些位置已经种上了高度相同的树k，每个位置最多有一棵树。砍倒位置x的树时，可以选择让树向左或向右倒下。如果向左倒，它会占据从x-k到x（包括x）的位置。如果向右倒，它会占据从x到x+k（包括x）的位置。给定m棵树在小巷上的位置x_1, x_2, ..., x_m。如果所有m棵树都可以被砍倒，且不倒在购物中心或道路上，并且每个位置最多只有一棵倒下的树，则称这样的小巷为“不幸的”。计算有多少种不同的“不幸的”小巷，其中种有m棵高度为k的树。如果存在一个位置y，在第一条小巷上有树，而在第二条小巷上没有树，则认为这两条小巷是不同的。输出结果对998,244,353取模。 输入数据格式： 输入只有一行，包含三个整数n, m和k（1 ≤ m, k ≤ n ≤ 3 × 10^5）——树木的位置数、树木的数量和每棵树的高度。 输出数据格式： 输出一个整数——有多少种不同的“不幸的”小巷，其中种有m棵高度为k的树，结果对998,244,353取模。