Minimums or Medians
Contest: VK Cup 2022 - Финальный раунд (Engine)
Difficulty rating: 3400

Vika has a set of all consecutive positive integers from $$$1$$$ to $$$2n$$$, inclusive.

Exactly $$$k$$$ times Vika will choose and perform one of the following two actions:

- take two smallest integers from her current set and remove them;
- take two median integers from her current set and remove them.

Recall that medians are the integers located exactly in the middle of the set if you write down its elements in increasing order. Note that Vika's set always has an even size, thus the pair of median integers is uniquely defined. For example, two median integers of the set $$$\{1, 5, 6, 10, 15, 16, 18, 23\}$$$ are $$$10$$$ and $$$15$$$.

How many different sets can Vika obtain in the end, after $$$k$$$ actions? Print this number modulo $$$998\,244\,353$$$. Two sets are considered different if some integer belongs to one of them but not to the other.

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^6$$$).

Output format:
Print a single integer — the number of sets Vika can obtain in the end, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, Vika's initial set is $$$\{1, 2, 3, 4, 5, 6\}$$$. She can remove the minimums from it to obtain $$$\{3, 4, 5, 6\}$$$, or she can remove the medians from it to obtain $$$\{1, 2, 5, 6\}$$$.

In the second example, Vika can obtain $$$\{1, 6\}$$$, $$$\{3, 6\}$$$, or $$$\{5, 6\}$$$. For instance, Vika can obtain $$$\{3, 6\}$$$ if she removes two smallest integers first ($$$\{1, 2, 3, 4, 5, 6\} \rightarrow \{3, 4, 5, 6\}$$$), and then she removes two median integers ($$$\{3, 4, 5, 6\} \rightarrow \{3, 6\}$$$).

In the third example, regardless of Vika's choices, she'll end up with an empty set.

Example input:
3 1

Example output:
2

Example input:
3 2

Example output:
3

Editorial:
Let's denote removing minimums with L, and removing medians with M. Now a sequence of Vika's actions can be described with a string $$$s$$$ of length $$$k$$$ consisting of characters L and M.
Observe that if we have a substring LMM, we can replace it with MLM, and the set of removed numbers will not change. We can keep applying this transformation until there are no LMM substrings in $$$s$$$.
Now, a string $$$s$$$ of our interest looks as a concatenation of:
1. $$$p$$$ letters M, for some $$$0 \le p \le k$$$;
2. if $$$p < k$$$, then a letter L;
3. $$$\max(0, k - 1 - p)$$$ letters L and M, without two letters M in a row.
Let's denote the number of letters M in part 3 above as $$$q$$$.
Can different strings still lead to equal sets in the end?
First, let's suppose that $$$k \le \frac{n - 1}{2}$$$. We will prove that all strings that match the above pattern result in distinct integer sets.
Part 1 in the above concatenation means that integers from $$$n-p+1$$$ to $$$n+p$$$ are removed. Since there are $$$k-p-q$$$ letters L in $$$s$$$ in total, integers from $$$1$$$ to $$$2(k-p-q)$$$ are removed too. However, integers in the range $$$[2(k-p-q) + 1; n-p]$$$ are not removed, and note that $$$2(k-p-q)+1 \le n-p$$$ is equivalent to $$$k \le \frac{n+p+2q-1}{2}$$$. Hence, this range is never empty when $$$k \le \frac{n - 1}{2}$$$. Thus, we can see that for all pairs of $$$p$$$ and $$$q$$$, the leftmost non-removed ranges are distinct.
Now, also note that in part 3 of the concatenation, any letter M always removes some two consecutive integers (since there is no substring MM), and letters L serve as "shifts" for these removals, and different sets of "shifts" result in different final sets of integers. This finishes the proof.
It is easy to find the number of ways to fill part 3 for fixed $$$p$$$ and $$$q$$$: there are $$$\binom{(k - 1 - p) - (q - 1)}{q}$$$ ways to choose $$$q$$$ positions out of $$$(k - 1 - p)$$$ so that no two consecutive positions are chosen. Now we have just iterate over all valid pairs of $$$p$$$ and $$$q$$$ to get an $$$O(n^2)$$$ solution for the $$$k \le \frac{n - 1}{2}$$$ case.
Before optimizing it to $$$O(n)$$$, let's get back to the $$$k > \frac{n - 1}{2}$$$ case. Some strings can result in the same final set. Let $$$x$$$ be the smallest integer in the final set. Note that $$$x$$$ is always odd. We will only look for a string that contains $$$\frac{x - 1}{2}$$$ letters L: that is, a string that removes integers from $$$1$$$ to $$$x-1$$$ only via removing minimums. We can see that there is always a unique such string.
Recall the uniqueness proof for $$$k \le \frac{n - 1}{2}$$$. When $$$p > 0$$$, we will now force that leftmost non-removed range, $$$[2(k-p-q) + 1; n-p]$$$, to be non-empty. If the range is empty, our sequence of actions does not satisfy the condition from the previous paragraph, so we can skip this pair of $$$p$$$ and $$$q$$$.
When $$$p = 0$$$, things are a bit different. Suppose we have fixed $$$q$$$. It means there are $$$k-q$$$ letters L in the string. These operations remove integers from $$$1$$$ to $$$2(k-q)$$$. Thus, we need the first letter M to remove integers strictly greater than $$$2(k-q)+1$$$, which gives us a lower bound on the number of letters L at the start of the string. Otherwise, we can use the same binomial coefficient formula for counting.
This should finish the $$$O(n^2)$$$ solution for any $$$k$$$.
To optimize it, let's iterate over $$$q$$$ first and iterate over $$$p$$$ inside. It turns out that all valid values of $$$p$$$ form a range, and if we look at what we are summing up, it is $$$\binom{0}{q} + \binom{1}{q} + \ldots + \binom{r}{q}$$$ for some integer $$$r$$$. This sum is equal to $$$\binom{r+1}{q+1}$$$ by the hockey-stick identity. Thus, we finally have an $$$O(n)$$$ solution.