AT_fps_24_s ゲーム

题目描述

我们定义如下“子问题”：

给定一棵有 $N$ 个结点（编号为 $1$ 到 $N$）的树，以及一个整数 $K$，其中 $K=1$ 或 $K=N$。 Alice 和 Bob 玩如下规则的游戏：

• 首先，Alice 将棋子放置在顶点 $1,2,\dots,K$ 之一；
• 然后，从 Bob 开始，两人轮流进行如下操作：
  • 选择当前棋子的相邻未访问过的一个顶点，并将棋子移动到那里；
• 若某人在其回合无法移动（即没有可走的相邻未访问顶点），则该人输，对方获胜。

假设两人都采取最优策略，判断谁最终获胜。

给定整数 $U$ 和 $\mathrm{type} \in \{1, 2\}$。 对于每个 $N = 2, 3, \dots, U$，解决如下问题：

• 给定整数 $N$ 和 $K$，其中 $K = 1$ 当 $\mathrm{type} = 1$，$K = N$ 当 $\mathrm{type} = 2$。 假设这些值对应上述子问题中的 $N$ 和 $K$。有 $N^{N-2}$ 种以 $1$ 到 $N$ 编号的所有树。 其中，有多少棵树能让子问题的答案为“Alice”？ 请将答案对 $998244353$ 取模输出。

输入格式

输入由标准输入给出，格式如下：

$U$ $\mathrm{type}$

输出格式

输出 $U-1$ 行，第 $i$ 行输出 $N=i+1$ 时的答案。

输入输出样例 #1

输入 #1

4 1

输出 #1

0
2
3

输入输出样例 #2

输入 #2

10 2

输出 #2

0
3
4
125
576
16807
154624
4782969
69760000

说明/提示

评分

本题的评分方式如下：

• 若你解出了所有 $\mathrm{type}=1$ 的数据，获得 $3$ 分。
• 若你解出了所有 $\mathrm{type}=2$ 的数据，获得 $3$ 分。

样例解释 1

当 $\mathrm{type}=1$ 时，始终有 $K=1$。 对于 $N=3$，一共有 $2$ 棵不同的树：一棵为边 $1-2-3$，另一棵为边 $1-3-2$。

样例解释 2

当 $\mathrm{type}=2$ 时，始终有 $K=N$。

数据范围

• $2 \leq U \leq 2.5 \times 10^5$
• $\mathrm{type} \in \{1, 2\}$
• 所有输入均为整数。

由 ChatGPT 5 翻译