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$ 时的答案。

## 评分 本题的评分方式如下： - 若你解出了所有 $\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 翻译