P9411 ‘STA - R2’ Gtrimee

Let $w_k(n)$ be the number of ordered rooted unlabeled trees whose children are ordered and that satisfy the following conditions: - The number of nodes $n_0\in[1,n]$. - All nodes with depth $k$ are not leaves. Given a fixed positive integer $k$, and then given a positive integer $n$ multiple times, compute $w_k(n)\bmod 998244353$. Here, the depth of a node is defined as the length of the unique simple path from it to the root. For example, the depth of the root is $0$.

**This problem has multiple queries.** The first line contains a positive integer $id$, indicating the Subtask ID. The second line contains two positive integers $q,k$, where $q$ is the number of queries. The next $q$ lines each contain one positive integer $n$, describing a query.

Output $q$ lines. Each line should be $w_k(n)\bmod 998244353$ for the corresponding query.

### Sample Explanation Explanation for Sample 1: When $k=2$, all valid trees with exactly $5$ nodes are:  ### Constraints **This problem uses bundled testdata.** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{Score} & \textbf{Special Properties}\\\hline \textsf{1} & 5 & 5 \\\hline \textsf{2} & 10^2 & 20\\\hline \textsf{3} & 2\times10^5 & 35 & k=1\\\hline \textsf{4} & 2\times10^5 & 40\\\hline\hline \end{array} $$ For all testdata, $1\le n,q,k\le 2\times10^5$. Translated by ChatGPT 5