Timber
Contest: Educational Codeforces Round 147 (Rated for Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, fft, math

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$$$.

Input format:
The 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.

Output format:
Print a single integer — the number of different unfortunate alleys with $$$m$$$ trees of height $$$k$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6 1 4

Example output:
4

Example input:
5 2 2

Example output:
0

Editorial:
People say that this problem can be bashed with generating functions. Sadly, I know nothing about them, so I'll explain the more adhoc solution I managed to come up.
Let's investigate the general form of some placement of trees. Imagine we fixed some position $$$x_1, x_2, \dots, x_m$$$ for them. How to check if it's possible to cut them all down? Well, it's a simple greedy problem. Process trees left to right. If a tree can fall down to the left, make it fall to the left. Otherwise, if it can fall down to the right, make it fall to the right. Otherwise, no answer.
Try a harder problem. Consider the spots the fallen trees take. How many constructions can these spots be induced by after the greedy algorithm is performed? First, these taken spots are actually segments of length $$$k+1$$$. Each tree can fall either from the left or the right side of the segment. To determine the answer, one has to look at the number of free spots to the left of each fallen tree. If there're at least $$$k$$$ free spots, then the tree can only fall from the left side of that segment. Otherwise, it can fall both ways. Thus, for $$$x$$$ trees that have less than $$$k$$$ free spots to the left of them, the answer is $$$2^x$$$.
We can't really iterate over the constructions, so let's try yet another related problem. Would be cool if we could fix the exact number of trees that have more than $$$k$$$ free cells to the left of them. I don't really know how to do that. But I know how to fix at least the amount. Let that be at least $$$x$$$ trees. For $$$x$$$ trees, make their segments of length $$$2k+1$$$ — $$$k+1$$$ for the tree itself and $$$k$$$ extra cells to the left of it. For the rest $$$m-x$$$ trees, make their segments of length $$$k+1$$$. Then we have to place them on the given $$$n$$$ spots. The path is as follows. Rearrange the long and the short segments among each other — $$$\binom{m}{x}$$$. Then use stars and bars to choose the amount of space between the segments — $$$\binom{n-x\cdot(2k+1)-(m-x)\cdot(k+1)+m}{m}$$$. Finally, multiply by $$$2^{m-x}$$$ to fix the side for the short segments.
Initially, we thought that we could just use PIE to calculate the exact answer from that — $$$\sum\limits_{x=0}^m f(x) \cdot (-1)^x$$$. And the results of this formula coincided with the naive solution, so we thought that everything should be fine. But unfortunately, even though the formula is right, using PIE in the described way is incorrect. Let us show you the correct way.
Let $$$F(x)$$$ be the number of ways to choose the segments for the trees in such a way that $$$x$$$ fixed segments are "long" (i. e. at least of length $$$2k+1$$$). To calculate $$$F(x)$$$, we use the familiar stars and bars concept: $$$\binom{n-x\cdot(2k+1)-(m-x)\cdot(k+1)+m}{m}$$$ (we already had this formula earlier).
Now, let $$$G(x)$$$ be the number of ways to choose the segments for the trees in such a way that $$$x$$$ fixed segments are "long", and all other segments are "short". The formula for $$$G(x)$$$ is a straightforward application of PIE: $$$G(x) = \sum\limits_{y=0}^{m-x} (-1)^y \binom{m-x}{y} F(x+y)$$$, where we iterate on $$$y$$$ — the number of segments that should be short, but are definitely long.
The answer to the problem can be calculated as $$$\sum\limits_{x=0}^{m} 2^{m-x} \binom{m}{x} G(x)$$$ — we choose which $$$x$$$ segments are "long", and all others should be "short". Expanding $$$G(x)$$$ gives us the following formula:
$$$$$$\sum\limits_{x=0}^m \sum\limits_{y=0}^{m-x} (-1)^y 2^{m-x} \binom{m}{x} \binom{m-x}{y} F(x+y)$$$$$$
which, after expanding binomial coefficients into factorials and getting rid of $$$(m-x)!$$$, becomes
$$$$$$\sum\limits_{x=0}^m \sum\limits_{y=0}^{m-x} (-1)^y 2^{m-x} \frac{m!}{x! y! (m-x-y)!} F(x+y)$$$$$$
We introduce the substitution variable $$$z = x + y$$$, and the formula becomes
$$$$$$\sum\limits_{z=0}^m \sum\limits_{y=0}^{z} (-1)^y 2^{m-z+y} \frac{m!}{(z-y)! y! (m-z)!} F(z)$$$$$$
By multiplying both the numerator and the denominator by $$$z!$$$, we then get
$$$$$$\sum\limits_{z=0}^m \sum\limits_{y=0}^{z} (-1)^y 2^{m-z+y} \binom{m}{z} \binom{z}{y} F(z)$$$$$$
$$$$$$\sum\limits_{z=0}^m \binom{m}{z} 2^{m-z} F(z) \sum\limits_{y=0}^{z} (-2)^y \binom{z}{y} F(z)$$$$$$
And $$$\sum\limits_{y=0}^{z} (-2)^y \binom{z}{y}$$$ is just $$$(1-2)^z$$$. Thus, the answer is equal to $$$\sum\limits_{z=0}^m (-1)^z \binom{m}{z} 2^{m-z} F(z)$$$.
Overall complexity: $$$O(n)$$$.