洞察（Insight）

Luogu

IDLGP10324

Time2000ms

Memory512MB

DifficultyP7

数学洛谷原创O2优化组合数学生成函数拉格朗日反演洛谷比赛

赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。 **** 在一个**无向连通图** $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。所有点都有标号，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。对于 $\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个： - $\text{type}=0$：无附加条件。 - $\text{type}=1$：对于每个**不包含**红色点的极大连通子图，都要对**恰好一个**点做特殊标记（每个标记也都是不同的）。答案对 $998244353$ 取模。 ## Input 输入一行两个整数 $n$ 和 $\text{type}$。 ## Output 输出一行一个整数表示答案。 [samples] ## Background 看待万物毫无偏见的新视角 —— 洞察。 **** 「洞察之光」凯伊·雅思·德·布拉德，是减法盗贼，也是背负黑暗命运的混沌骑士。凯伊的右手内隐藏着混沌之剑，为了使其发挥出足够的力量又不至于失控，需要满足特定的内部结构。她想知道有多少种符合条件的结构，为了方便你的计算，她把问题转化为如下形式： ## Note 【样例 $1$ 解释】此时 $\text{type}=1$，所有 $5$ 种合法的图包括： 1. $R-W'-B$ 2. $R-W-B'$ 3. $R-B'-W$ 4. $R-B-W'$ 5. $B'-R-W'$ 由于 $n=1$，可以仅用 $B$ 和 $W$ 来区分白点和黑点，$R$ 表示红点。中间的横杠表示连边，$B'$ 和 $W'$ 分别表示有标记的白点和黑点。注意，由于第 $5$ 个图中，单个的 $B$ 和 $W$ 就是不包含 $R$ 的极大连通子图，必须各有一个标记在这唯一的位置上。【样例 $2,3$ 解释】见附件图片，其中展示了 $\text{type}=0$ 时全部的 $45$ 种可能的图 $G$。对于 $\text{type}=1$ 的情况，只需要对每个图的基础上做标记，就可以数出答案为 $149$。【样例 $4,5$ 解释】取模前的答案分别为 $116758263583336861101$ 和 $4159784334433940020473603987503242886367209494283213841$。【数据范围】 **本题采用捆绑测试。** Subtask 1（8 pts）：$n \le4$； Subtask 2（10 pts）：$n \le 10^3$，$\text{type}=0$； Subtask 3（11 pts）：$\text{type}=0$； Subtask 4（13 pts）：$n \le 100$，$\text{type}=1$； Subtask 5（14 pts）：$n \le 10^3$，$\text{type}=1$； Subtask 6（21 pts）：$n\le 10^5$，$\text{type}=1$； Subtask 7（23 pts）：$\text{type}=1$。对于全部的数据，$1\le n \le 10^7$，$\text{type}\in \{ 0,1\}$。【提示】对于这类题目，你或许会想从 [OEIS](https://oeis.org/) 上寻找答案。但我要提醒你的是，直接搜索答案数列不会找到任何结果。然而，对于小数据范围，仍然可以提前处理出答案数列。

Samples

Input #1

1 1

Output #1

Input #2

2 0

Output #2

Input #3

2 1

Output #3

Input #4

10 0

Output #4

36011666

Input #5

20 1

Output #5

593465999

Input #6

106 1

Output #6

516553582

API Response (JSON)

{
  "problem": {
    "name": "洞察（Insight）",
    "description": {
      "content": "赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。 **** 在一个**无向连通图** $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。   所有点都有标号，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。 对于 $\\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个： - $\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10324"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。\n****\n在一个**无向连通图** $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。  \n所有点都有标号，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。\n\n对于 $\\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个：\n\n- $\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments