ZS Shuffles Cards
Contest: Codeforces Global Round 10
Difficulty rating: 3000
Tags: combinatorics, dp, math, probabilities

zscoder has a deck of $$$n+m$$$ custom-made cards, which consists of $$$n$$$ cards labelled from $$$1$$$ to $$$n$$$ and $$$m$$$ jokers. Since zscoder is lonely, he wants to play a game with himself using those cards.

Initially, the deck is shuffled uniformly randomly and placed on the table. zscoder has a set $$$S$$$ which is initially empty.

Every second, zscoder draws the top card from the deck.

- If the card has a number $$$x$$$ written on it, zscoder removes the card and adds $$$x$$$ to the set $$$S$$$.
- If the card drawn is a joker, zscoder places all the cards back into the deck and reshuffles (uniformly randomly) the $$$n+m$$$ cards to form a new deck (hence the new deck now contains all cards from $$$1$$$ to $$$n$$$ and the $$$m$$$ jokers). Then, if $$$S$$$ currently contains all the elements from $$$1$$$ to $$$n$$$, the game ends. Shuffling the deck doesn't take time at all.

What is the expected number of seconds before the game ends? We can show that the answer can be written in the form $$$\frac{P}{Q}$$$ where $$$P, Q$$$ are relatively prime integers and $$$Q \neq 0 \bmod 998244353$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.

Input format:
The only line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^{6}$$$).

Output format:
Output a single integer, the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.

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

Note:
For the first sample, it can be proven that the expected time before the game ends is $$$5$$$ seconds.

For the second sample, it can be proven that the expected time before the game ends is $$$\frac{28}{3}$$$ seconds.

Example input:
2 1

Example output:
5

Example input:
3 2

Example output:
332748127

Editorial:
Firstly, let's find a simple dp. Let $$$f(x)$$$ denote the expected time before the game ends with the deck is full (with $$$n+m$$$ cards) and $$$S$$$ contains $$$n - x$$$ elements. Hence, $$$f(0)=0$$$. Our goal is to find $$$f(n)$$$.
Suppose the jokers are also numbered from $$$1$$$ to $$$m$$$ and $$$S$$$ contains $$$n-x$$$ elements. Consider the cards drawn before we draw our first joker (which causes the deck to be reshuffled). Suppose we draw $$$i$$$ cards with a number, $$$l$$$ of which is a number not in $$$S$$$, before drawing our first joker. There are $$$\binom{x}{l} \cdot \binom{n-x}{i-l} \cdot i!$$$ ways to choose and permute the first $$$i$$$ cards, $$$m$$$ ways to choose the first joker and $$$(n+m-i-1)!$$$ ways to permute the cards that were not drawn. The total time taken is $$$i+1+f(x-l)$$$. Hence,
$$$f(x) = \displaystyle\sum_{l=0}^{x}\displaystyle\sum_{i=0}^{n}\binom{x}{l}\binom{n-x}{i-l} \cdot i! \cdot m \cdot \frac{(n+m-i-1)!}{(n+m)!} \cdot (f(x-l)+i+1).$$$
This gives us an easy $$$O(n^{3})$$$ solution. Note that $$$f(x)$$$ is also on the right hand side, so you need to move the corresponding term to the left first before computing (this is not difficult).
To optimize our solution, we just need to manipulate the sums. I will show how to simplify $$$\displaystyle\sum_{l=0}^{x}\displaystyle\sum_{i=0}^{n}\binom{x}{l}\binom{n-x}{i-l} \cdot i! \cdot m \cdot \frac{(n+m-i-1)!}{(n+m)!} \cdot (i+1)$$$. The way to simplify $$$\displaystyle\sum_{l=0}^{x}\displaystyle\sum_{i=0}^{n}\binom{x}{l}\binom{n-x}{i-l} \cdot i! \cdot m \cdot \frac{(n+m-i-1)!}{(n+m)!} \cdot f(x-l)$$$ is analogous.
We have
$$$\displaystyle\sum_{l=0}^{x}\displaystyle\sum_{i=0}^{n}\binom{x}{l}\binom{n-x}{i-l} \cdot i! \cdot m \cdot \frac{(n+m-i-1)!}{(n+m)!} \cdot (i+1)$$$
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \displaystyle\sum_{l=0}^{x}\frac{1}{l!(x-l)!} \displaystyle \sum_{i=0}^{n}\frac{(i+1)! \cdot (n+m-i-1)!}{(i-l)! \cdot (n-x-i+l)!}$$$ (expanding and regrouping)
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \displaystyle\sum_{l=0}^{x}\frac{(m-1+x-l)!(l+1)}{(x-l)!} \displaystyle \sum_{i=0}^{n}\frac{(i+1)!}{(l+1)!(i-l)!} \cdot \frac{(n+m-i-1)!}{(n-x-i+l)!(m-1+x-l)!}$$$ (making binomial coefficients appear)
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \displaystyle\sum_{l=0}^{x}\frac{(m-1+x-l)!(l+1)}{(x-l)!} \displaystyle \sum_{i=0}^{n}\binom{i+1}{l+1}\binom{n+m-i-1}{m-1+x-l}$$$
Recall that $$$\displaystyle\sum_{i}\binom{i}{a}\binom{n-i}{b-a} = \binom{n+1}{b+1}$$$, because we can count the right hand side by fixing the position of the $$$(a+1)$$$-th element, where $$$i$$$ denotes the number of elements on the left of the $$$(a+1)$$$-th element.
Hence,
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \displaystyle\sum_{l=0}^{x}\frac{(m-1+x-l)!(l+1)}{(x-l)!} \cdot \binom{n+m+1}{m+x+1}$$$
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \binom{n+m+1}{m+x+1} \cdot \displaystyle\sum_{l=0}^{x}\frac{(m-1+x-l)!}{(x-l)!} \cdot (l+1)$$$
$$$= \frac{m \cdot x! \cdot (n-x)!}{(n+m)!} \cdot \binom{n+m+1}{m+x+1} \cdot \displaystyle\sum_{l=0}^{x}\frac{(m-1+l)!}{l!} \cdot (x-l+1)$$$.
We can compute the latter sum in $$$O(1)$$$ via prefix sums (after splitting $$$x+1$$$ and $$$-l$$$). A similar computation can be done for $$$\displaystyle\sum_{l=0}^{x}\displaystyle\sum_{i=0}^{n}\binom{x}{l}\binom{n-x}{i-l} \cdot i! \cdot m \cdot \frac{(n+m-i-1)!}{(n+m)!} \cdot f(x-l)$$$.
Hence, $$$f(x)$$$ can be computed in $$$O(1)$$$ (with prefix sums) for $$$x=1$$$ to $$$n$$$. This gives a $$$O(n+m)$$$ time solution if you precompute factorials.