AT_pakencamp_2025_day1_p Champion

若一个 $N \times N$ 的 $01$ 矩阵 $P$ 满足以下条件，则称 $P$ 为 **League 矩阵**： - $P_{i,i} = 0$ （$1 \leq i \leq N$） - $P_{i,j} + P_{j,i} = 1$ （$1 \leq i < j \leq N$） 此外，可以从某个 League 矩阵 $P$ 构造一个有 $N$ 个顶点、$N(N-1)/2$ 条边的有向图 $G$，具体如下： - 当 $P_{i,j} = 1$ 时，在 $G$ 中从顶点 $j$ 向顶点 $i$ 连一条有向边。 在 $G$ 中，入度最大的顶点（如果有多个则全部算上）被称为 **Champion**，满足下列之一的顶点被称为 **Champion?**： - 是 Champion； - 存在从某个 Champion 出发沿若干条边可以到达该顶点。 现从所有可能的 $N\times N$ 的 League 矩阵中等概率随机选出一个，求被选中时 Champion? 顶点的个数的期望值，对 $998244353$ 取模后输出。

输入为标准输入，格式如下： > $N$

请输出一行答案。

### 部分分 若你能正确解决满足以下限制的测试点，将获得 $300$ 分： - $1 \leq N \leq 2000$ ### 样例解释 1 例如，当矩阵如下时： ``` 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$ 号两个，它们都是 Champion，同时也是 Champion?。 - 顶点 $3$ 可以从 Champion 的顶点 $1$ 经过 $1 \to 3$ 到达，所以是 Champion?。 - 顶点 $5$ 可以从 Champion 的顶点 $1$ 经 $1 \to 3 \to 5$ 到达，所以是 Champion?。 - 顶点 $4$ 无法从任一 Champion 沿边到达，所以不是 Champion?。 因此，这种情况下 Champion? 的顶点个数为 $4$。$5 \times 5$ 的 League 矩阵总数为 $2^{10}=1024$，所以随机选一个时 Champion? 的顶点个数期望为 $\frac{455}{128}$，对 $998244353$ 取模后为 $444530692$，请输出该值。 ### 样例解释 2 能构造的有向图有 $2^1 = 2$ 种情况，在这两种情况下 Champion? 的顶点数均为 $1$。 ### 样例解释 4 本案例中 $N>2000$，不影响部分分。 ### 约束条件 - $1 \leq N \leq 2 \times 10^5$ - 输入均为整数。 由 ChatGPT 5 翻译