分数: 6 点
问题陈述
我们将以下定义为 子问题:
你有一棵树 N 顶点标记 1 通过 N,和一个整数 K 其中 K=1 or 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 if \mathrm{type} = 1,和 K = N if \mathrm{type} = 2.
假设这些值与 上述子问题的 N 和 K 。有 N^{N-2} 可能的树 N 顶点标记 1 通过 N.
其中,统计有多少棵树给出子问题的答案“Alice”,并输出结果模 998244353.
约束
- 2 \leq U \leq 2.5 \times 10^5
- \mathrm{type} \in {1, 2}
- 所有输入值均为整数
评分
该问题有以下评分规则:
- 如果您使用以下方法求解所有数据集 \mathrm{type} = 1,您将获得 3 点。
- 如果您使用以下方法求解所有数据集 \mathrm{type} = 2,您将获得 3 点。
输入
输入由标准输入给出,格式如下:
U \mathrm{type}
输出
打印 U - 1 行。上 i第行,输出答案 N = i + 1.
示例输入 1
4 1
示例输出 1
0 2 3
当 \mathrm{type} = 1, K = 1 始终成立。
对于 N = 3,有 2 有效树:一棵有边的树 1-2-3,另一个有边缘 1-3-2.
示例输入 2
10 2
示例输出 2
0 3 4 125 576 16807 154624 4782969 69760000
当 \mathrm{type} = 2, K = N 始终成立。