P17618 [Math+Girl×1] dancing With Myself in the sunset / Wheels Mst
题目背景
[](https://www.bilibili.com/video/BV1XZQ1YHEkN)
> *在黄昏里醒来的时候找不到自己了。*
题目描述
给定 $n$，定义*轮图* $W_{n+1}$ 是无向图，点集 $0\sim n$，其中 $1\sim n$ 依次连成环，$0$ 和其余每个点连边，共 $2n$ 条边。
对于 $\left[3,\left\lfloor\dfrac n2\right\rfloor+1\right]$ 中的每个 $x$，求在 $W_{n+1}$ 上加边 $(1,x)$ 后得到的新图中，所有 $(2n+1)!$ 种给边赋上 $[1,2n+1]$ 的不同整数边权的方案中，*最小生成树*的权值和之和 $\operatorname{mod}998244353$。
输入格式
一行一个正整数 $n$。
输出格式
一行 $\left\lfloor\dfrac n2\right\rfloor-1$ 个整数，第 $i$ 个数表示 $x=i+2$ 时的答案，对 $998244353$ 取模。
说明/提示
### 数据范围与约定
**本题采用捆绑测试。**
::cute-table{tuack}
| 子任务 | $n\le$ | 分值 |
|:-----:|:------:|:---:|
| $1$ | $10$ | $10$ |
| $2$ | $10^2$ | $30$ |
| $3$ | $10^3$ | $20$ |
| $4$ | $10^5$ | $10$ |
| $5$ | $10^6$ | $10$ |
| $6$ | $2\times 10^7$ | $20$ |
对于所有数据，$4\le n\le2\times10^7$。
**请注意常数因子对运行效率的影响。**