配点 : 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 ,因此不影响部分点。