P5162 WD and Building Blocks

WD is immersed in building blocks all day and cannot stop...

WD wants to buy $n$ building blocks. In the store, each block has height $1$, and its top view is a square (the side length is not necessarily the same). For some special reasons, the seller will randomly assign each block a size and a label, and give them to WD. Next, WD will put blocks of the same size into one layer, and stack all layers from large to small. WD wants to know the expected number of layers among all different stacking methods. **Two stacking methods are different if and only if some block is in a different layer in the two methods. Since WD only cares about the relative sizes of the blocks, all stacking methods are equally likely, rather than all random size assignments being equally likely (you can understand this from the samples).** Output the result $\bmod \space 998244353$. (If you still cannot understand the statement, please look at the samples.)

The first line contains an integer $T$, the number of queries. Then follow $T$ lines, each containing an integer $n$, meaning WD wants to use $n$ building blocks.

Output $T$ lines. Each line contains one integer, the answer $\bmod \space 998244353$.

In the following, curly braces denote blocks placed in the same layer. For $n=1$, the only valid arrangement is $\{1\}$. For $n=2$, the valid sequences are $\{1,2\}$, $\{1\}\{2\}$, $\{2\}\{1\}$. The expected number of layers is $\frac{1+2+2}{3}=665496237(mod~998244353)$. For $n=3$, the valid sequences are $\{1\}\{2\}\{3\}$, $\{1\}\{3\}\{2\}$, $\{2\}\{1\}\{3\}$, $\{2\}\{3\}\{1\}$, $\{3\}\{1\}\{2\}$, $\{3\}\{2\}\{1\}$, $\{1,2\}\{3\}$, $\{1,3\}\{2\}$, $\{2,3\}\{1\}$, $\{1\}\{2,3\}$, $\{2\}\{1,3\}$, $\{3\}\{1,2\}$, $\{1,2,3\}$, for a total of 13 types. Therefore, the expectation is $\frac{6\times3+6\times2+1}{13}=307152111(mod~998244353)$. ~~For $n=4$, I have a wonderful explanation, but unfortunately there is not enough space to write it here.~~ $subtask1(21pts):~1\le T\le 1,000,~1\le n\le 1,000$ $subtask2(37pts):~1\le T\le 10,~1\le n\le 100,000$ $subtask3(42pts):~1\le T\le 100,000,~1\le n\le 100,000$ Translated by ChatGPT 5