{"problem":{"name":"『STA - R2』Gtrimee","description":{"content":"令满足如下条件的儿子有序的无标号有根树数量为 $w_k(n)$： - 点数 $n_0\\in[1,n]$。 - 所有深度为 $k$ 的点都不是叶子。 给定固定正整数 $k$，多次给定正整数 $n$，求 $w_k(n)\\bmod 998244353$ 的值。 此处一个点的深度定义为它到根的唯一简单路径的长度，比如根的深度就是 $0$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":196608},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9411"},"statements":[{"statement_type":"Markdown","content":"令满足如下条件的儿子有序的无标号有根树数量为 $w_k(n)$：\n- 点数 $n_0\\in[1,n]$。\n- 所有深度为 $k$ 的点都不是叶子。\n\n给定固定正整数 $k$，多次给定正整数 $n$，求 $w_k(n)\\bmod 998244353$ 的值。\n\n此处一个点的深度定义为它到根的唯一简单路径的长度，比如根的深度就是 $0$。\n\n## Input\n\n**本题有多组询问。**\n\n第一行一个正整数 $id$ 表示 Subtask 编号。\n\n第二行两个正整数 $q,k$，其中 $q$ 表示询问次数。\n\n后 $q$ 行，每行一个正整数 $n$，描述一组询问。\n\n## Output\n\n$q$ 行，每行对应一个 $w_k(n)\\bmod 998244353$。\n\n[samples]\n\n## Note\n\n### 样例解释\n样例 1 解释：\n\n$k=2$，树上恰有 $5$ 个点时的所有方案：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/pwgn6z92.png)\n### 数据范围\n**本题采用捆绑测试。**\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\bm{n}\\le & \\textbf{分值} & \\textbf{特殊性质}\\\\\\hline\n\\textsf{1} & 5 & 5  \\\\\\hline\n\\textsf{2} & 10^2 & 20\\\\\\hline\n\\textsf{3} & 2\\times10^5 & 35 & k=1\\\\\\hline\n\\textsf{4} & 2\\times10^5 & 40\\\\\\hline\\hline\n\\end{array}\n$$\n\n对于全部数据，$1\\le n,q,k\\le 2\\times10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9411","tags":["多项式","O2优化","Catalan 数","生成函数"],"sample_group":[["0\n5 2\n1\n2\n3\n4\n5","1\n2\n3\n5\n10"],["0\n5 200\n1\n10\n100\n1000\n10000","1\n6918\n721868074\n972431902\n815282281"]],"created_at":"2026-03-03 11:09:25"}}