← 返回题目列表

AtCoder · fps_24_s

S. 游戏

中文机器翻译题面 查看原题

分数: 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 始终成立。