← 返回题目列表

AtCoder · pakencamp_2025_day1_p

P. 冠军

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

配点 : 600 点

問題文

N × N 矩阵 当 P 满足以下条件时, P 是 您也可以写 联赛矩阵 假设它是 。

  • P_{i,i} = 0 (1 \leq i \leq N)
  • P_{i,j} + P_{j,i} = 1 (1 \leq i < j \leq N)

另外,还有一个联赛矩阵 P 如下 N 頂点 N(N-1)/2 边的有向图 您将得到 G 。 当

  • P_{i,j} = 1 当时 G 顶点在 j 到顶点 i 绘制一条有向边

在这里, G ,选择入度最高的顶点(如果有多个则全部选择) 冠军 ,满足以下任一条件的顶点为 冠军? 。

  • 冠军
  • 可以通过从某个冠军顶点追踪一些边来到达。

一切皆有可能 来自 N × N 的联盟矩阵 1 当随机选择一个时,冠军顶点数量的期望值? 使用 \mathrm{mod} 998244353 找到它。

制約

  • 1 \leq N \leq 2×10^5
  • 所有输入均为整数

部分点

如果满足以下附加约束的测试用例得到正确回答, 300 点。 如果您正确回答了所有满足

  • 1 \leq N \leq 2000

入力

输入是按以下格式从标准输入给出的。

N

出力

将答案输出在一行。


入力例 1

5

出力例 1

444530692

例如,考虑以下矩阵。

0 1 0 1 1
0 0 1 1 1
1 0 0 1 0
0 0 0 0 0
0 0 1 1 0

此时Champion和Champion的顶点?对应的有向图如下。

  • 首先入度最大的顶点为顶点 1 和 按字典顺序比较 2 可以得到第 2 和这个 2 巅峰就是冠军,同时也是冠军?
  • 頂点 3 是冠军的顶点 1 减去 1 → 3 并且可以沿着边缘移动,所以它是冠军?
  • 頂点 5 是冠军的顶点 1 减去 1 → 3 → 5 并且可以沿着边缘移动,所以它是冠军?
  • 頂点 4 不是冠军?因为它不能通过跟随任何冠军顶点的边来移动。

因此,冠军的顶点数量是多少?在这种情况下是 4 一。 请注意,无法创建 5 × 5 的联盟矩阵为 有 2^{10} = 1024 个数字,但是是随机的 1 冠军顶点数量的期望值?当其中一个被选中时 \frac{455}{128} 所以, 您最多只能移动到 \mathrm{mod} 998244353 在上面表达这一点 444530692 请输出。


入力例 2

2

出力例 2

1

可以被视为有向图的是 2^1 = 2 并且在两种情况下都是冠军的顶点数量是 1 。


入力例 3

100

出力例 3

550420818

入力例 4

2026

出力例 4

926770690

这个案例是 N 是 在 2000 ,因此不影响部分点。