Card Guessing
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2600
Tags: combinatorics, dp, probabilities

Consider a deck of cards. Each card has one of $$$4$$$ suits, and there are exactly $$$n$$$ cards for each suit — so, the total number of cards in the deck is $$$4n$$$. The deck is shuffled randomly so that each of $$$(4n)!$$$ possible orders of cards in the deck has the same probability of being the result of shuffling. Let $$$c_i$$$ be the $$$i$$$-th card of the deck (from top to bottom).

Monocarp starts drawing the cards from the deck one by one. Before drawing a card, he tries to guess its suit. Monocarp remembers the suits of the $$$k$$$ last cards, and his guess is the suit that appeared the least often among the last $$$k$$$ cards he has drawn. So, while drawing the $$$i$$$-th card, Monocarp guesses that its suit is the suit that appears the minimum number of times among the cards $$$c_{i-k}, c_{i-k+1}, \dots, c_{i-1}$$$ (if $$$i \le k$$$, Monocarp considers all previously drawn cards, that is, the cards $$$c_1, c_2, \dots, c_{i-1}$$$). If there are multiple suits that appeared the minimum number of times among the previous cards Monocarp remembers, he chooses a random suit out of those for his guess (all suits that appeared the minimum number of times have the same probability of being chosen).

After making a guess, Monocarp draws a card and compares its suit to his guess. If they match, then his guess was correct; otherwise it was incorrect.

Your task is to calculate the expected number of correct guesses Monocarp makes after drawing all $$$4n$$$ cards from the deck.

Input format:
The first (and only) line contains two integers $$$n$$$ ($$$1 \le n \le 500$$$) and $$$k$$$ ($$$1 \le k \le 4 \cdot n$$$).

Output format:
Let the expected value you have to calculate be an irreducible fraction $$$\dfrac{x}{y}$$$. Print one integer — the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is the inverse to $$$y$$$ (i. e. an integer such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

Constraints:
Time limit: 15.0 s
Memory limit: 1024.0 MB

Example input:
1 1

Example output:
748683266

Example input:
3 2

Example output:
567184295

Editorial:
Obviously, linearity of expectation, we are calculating the sum of probability to guess correctly for each position from $$$1$$$ to $$$4n$$$.
Let's start with a minor observation which can help us in calculations. The probability for all positions from $$$k+1$$$ onwards is the same. The probability for each position $$$i$$$ depends on the number of ways (and some properties of them) to pick $$$\min(i - 1, k)$$$ cards prior to it. Thus, when this $$$\min$$$ evaluates to $$$k$$$, it's all the same. We'll calculate the first $$$k+1$$$ positions and then multiply the last one by $$$4n - k$$$.
How about we start with a naive solution? Let's pretend all cards are distinguishable from each other (which, in my opinion, is a rare case for combinatorics solutions). Then we can pick $$$a$$$ cards of the first suit, $$$b$$$ cards of the second suit, $$$c$$$ cards of the third suit and $$$d$$$ cards of the fourth suit to go prior to the position $$$a + b + c + d$$$. Check if the sum doesn't exceed $$$k$$$.
The number of ways to choose these cards is $$$C(n, a) \cdot C(n, b) \cdot C(n, c) \cdot C(n, d) \cdot (a + b + c + d)!$$$. We should also permute the remaining cars — multiply by $$$(4n - (a + b + c + d))!$$$. And divide everything by $$$(4n)!$$$ to get the probability of getting exactly that permutation. The probability to guess the suit correctly is $$$\frac{\min(a, b, c, d)}{4n - (a + b + c + d)}$$$. Thus, we should add the product of these two probabilities to the answer.
The annoying aspect of this solution is actually the $$$\min$$$ function. We'd prefer to always know that $$$a$$$ is the smallest one. Let's try to rewrite this naive in such a way that $$$a \le b \le c \le d$$$.
Frankly, almost nothing changes. To account for the fact that we removed the order of $$$a, b, c$$$ and $$$d$$$, we want to multiply the number of ways by the number of ways to permute these amounts. That number is a multinomial that depends on the sizes of equivalence classes of the amounts. As in, if the amounts are $$$1, 1, 2, 3$$$, then it's $$$\frac{4!}{2! \cdot 1! \cdot 1!}$$$. If it's $$$1, 1, 1, 3$$$, then it's $$$\frac{4!}{3! \cdot 1!}$$$. All the rest stays the same. Then the probability to guess correctly is just $$$\frac{a}{4n - (a + b + c + d)}$$$.
Great, now we can make a dp out of this naive solution. Basically, the answer depends on three things. The smallest amount, the total amount, and the counts of each amount. The first one can be accounted for during the initialization phase. The second one can be accounted for at the very end. And the third one can be accounted for during the transition :)
We want to construct non-decreasing sequences of length $$$4$$$ with a known sum and with a known first element. Let that $$$dp$$$ be $$$dp[i][j][k]$$$ — some sum of probabilities over all sequences such that the current amount is $$$i$$$, the sum of the sequence is $$$j$$$, and we placed $$$k$$$ elements in the sequence.
For the transition, we want to either increase the current value $$$i$$$ by $$$1$$$, or to place from $$$1$$$ to $$$4 - k$$$ copies of the current value. If we place it, we immediately apply the cnk and divide by the multinomial coefficient — the factorial of the number of copies. We increase $$$i$$$ as well, so that we can't place more elements equal to $$$i$$$.
For the initialization, we iterate over the smallest element and the count of it. This way, we can put the numerator of the probability to guess the suit along with the other things.
When we collect the answers, we iterate over the sum and account for the rest of the terms in the product: factorial of the sum, permuting the remaining cards, the denominator of the guess probability and so on.
The formulas might get tricky, but they all make enough sense, and hopefully nothing incorrect works on the examples, which should help you to debug.
Overall complexity: $$$O(n^2)$$$.
There are cubic solutions, that are also smart enough in our opinion, which is why the constraints are set like that.