『STA - R2』Gtrimee

Luogu

IDLGP9411

Time4000ms

Memory192MB

DifficultyP7

多项式O2优化Catalan 数生成函数

令满足如下条件的儿子有序的无标号有根树数量为 $w_k(n)$： - 点数 $n_0\in[1,n]$。 - 所有深度为 $k$ 的点都不是叶子。给定固定正整数 $k$，多次给定正整数 $n$，求 $w_k(n)\bmod 998244353$ 的值。此处一个点的深度定义为它到根的唯一简单路径的长度，比如根的深度就是 $0$。 ## Input **本题有多组询问。** 第一行一个正整数 $id$ 表示 Subtask 编号。第二行两个正整数 $q,k$，其中 $q$ 表示询问次数。后 $q$ 行，每行一个正整数 $n$，描述一组询问。 ## Output $q$ 行，每行对应一个 $w_k(n)\bmod 998244353$。 [samples] ## Note ### 样例解释样例 1 解释： $k=2$，树上恰有 $5$ 个点时的所有方案： ![](https://cdn.luogu.com.cn/upload/image_hosting/pwgn6z92.png) ### 数据范围 **本题采用捆绑测试。** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}\\\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} $$ 对于全部数据，$1\le n,q,k\le 2\times10^5$。

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "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第一行一个正...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments