Happy Sets
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: combinatorics

Define a set $$$A$$$ as a child of set $$$B$$$ if and only if for each element of value $$$x$$$ that is in $$$A$$$, there exists an element of value $$$x+1$$$ that is in $$$B$$$.

Given integers $$$N$$$ and $$$K$$$. In order to make Chaneka happy, you must find the number of different arrays containing $$$N$$$ sets $$$[S_1, S_2, S_3, \ldots, S_N]$$$ such that: - Each set can only contain zero or more different integers from $$$1$$$ to $$$K$$$. - There exists a way to rearrange the order of the array of sets into $$$[S'_1, S'_2, S'_3, \ldots, S'_N]$$$ such that $$$S'_i$$$ is a child of $$$S'_{i+1}$$$ for each $$$1\leq i\leq N-1$$$.

Print the answer modulo $$$998\,244\,353$$$.

Two sets are considered different if and only if there is at least one value that only occurs in one of the two sets.

Two arrays of sets are considered different if and only if there is at least one index $$$i$$$ such that the sets at index $$$i$$$ in the two arrays are different.

Input format:
The only line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N,K \leq 2\cdot10^5$$$) — the number of sets in the array and the maximum limit for the values in the sets.

Output format:
An integer representing the number of different arrays of sets that satisfy the problem condition, modulo $$$998\,244\,353$$$.

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

Note:
In the first example, there are $$$11$$$ different arrays of sets possible, which are:

- $$$[\{\}, \{\}]$$$
- $$$[\{\}, \{1\}]$$$
- $$$[\{\}, \{1, 2\}]$$$
- $$$[\{\}, \{2\}]$$$
- $$$[\{1\}, \{\}]$$$
- $$$[\{1\}, \{1, 2\}]$$$
- $$$[\{1\}, \{2\}]$$$
- $$$[\{1, 2\}, \{\}]$$$
- $$$[\{1, 2\}, \{1\}]$$$
- $$$[\{2\}, \{\}]$$$
- $$$[\{2\}, \{1\}]$$$

Example input:
2 2

Example output:
11

Example input:
1 3

Example output:
8

Editorial:
First, consider all possible arrays $$$S'$$$ (the array of sets after rearranging). For each valid $$$S'$$$, we want to find the number of ways to shuffle it. The answer to the original problem is equal to the sum of ways to shuffle each possible $$$S'$$$, since for each shuffled $$$S'$$$ it can be shown that there is only one way to rearrange it into a valid $$$S'$$$.
Notice that a valid $$$S'$$$ always consists of a group of empty sets and a group of pairwise distinct non-empty sets. That means, if there are $$$e$$$ empty sets, then there are $$$\frac{N!}{e!}$$$ ways to shuffle $$$S'$$$.
From the knowledge above, we can group all possible valid arrays $$$S'$$$ into groups based on the number of empty sets and count the number of valid arrays $$$S'$$$ in each group. Then for each group, multiply the number of valid arrays $$$S'$$$ by the number of ways to shuffle $$$S'$$$ for that number of empty sets, then add it to the answer.
Now, define $$$f(e)$$$ as the number of valid arrays $$$S'$$$ with exactly $$$e$$$ empty sets. Define $$$g(e)$$$ as the number of valid arrays $$$S'$$$ with at least $$$e$$$ empty sets. We get that $$$f(e)=g(e)-g(e+1)$$$.
Let's calculate $$$g(e)$$$. For an array of sets $$$S'$$$, we can consider it as a set of pairs $$$(p,x)$$$, where each pair $$$(p,x)$$$ denotes that $$$S'_p$$$ contains $$$x$$$. Notice that for some value $$$x$$$:
• $$$(N-1,x-1)$$$ can only exist if $$$(N,x)$$$ exists.
• $$$(N-2,x-2)$$$ can only exist if $$$(N-1,x-1)$$$ exists.
• $$$(N-3,x-3)$$$ can only exist if $$$(N-2,x-2)$$$ exists.
• And so on.
Therefore, we can group the possible pairs into groups $$$[(N,x),(N-1,x-1),(N-2,x-2),\ldots]$$$ and for every group, if it has $$$c$$$ pairs, then there are only $$$c+1$$$ configurations for that group (only the first $$$i$$$ pairs exist for every $$$0\leq i\leq c$$$). The total number of configurations is the product of $$$c+1$$$ for every group.
Consider the size of each group. There are only $$$K$$$ groups, each starts with $$$(N,x)$$$ for every $$$1\leq x\leq K$$$. The group that starts with $$$(N,x)$$$ has $$$\min(x,N-e)$$$ possible pairs. That means, the size of each group is $$$[1,2,3,\ldots,N-e-2,N-e-1,N-e,N-e,N-e,\ldots]$$$. Therefore, $$$g(e)=(N-e+1)!(N-e+1)^{(K-(N-e))}$$$. We can calculate all values of $$$g(e)$$$ using factorial precomputation and binary exponentiation.
Time complexity: $$$O(N\log K)$$$