33OJ
登录 注册

#P17618. [Math+Girl×1] dancing With Myself in the sunset / Wheels Mst

[Math+Girl×1] dancing With Myself in the sunset / Wheels Mst

背景

在黄昏里醒来的时候找不到自己了。

题目描述

给定 nn,定义轮图 Wn+1W_{n+1} 是无向图,点集 0∼n0\sim n,其中 1∼n1\sim n 依次连成环,00 和其余每个点连边,共 2n2n 条边。

对于 $\left[3,\left\lfloor\dfrac n2\right\rfloor+1\right]$ 中的每个 xx,求在 Wn+1W_{n+1} 上加边 (1,x)(1,x) 后得到的新图中,所有 (2n+1)!(2n+1)! 种给边赋上 [1,2n+1][1,2n+1] 的不同整数边权的方案中,最小生成树的权值和之和 mod⁡998244353\operatorname{mod}998244353。

输入格式

一行一个正整数 nn。

输出格式

一行 ⌊n2⌋−1\left\lfloor\dfrac n2\right\rfloor-1 个整数,第 ii 个数表示 x=i+2x=i+2 时的答案,对 998244353998244353 取模。

4
3857760
8
274314254 900658981 141086820
12
844621131 708548915 317841275 124930753 731097448
18
744963935 210055227 439652156 868477371 389817015 690785547 276112964 215894660

提示

数据范围与约定

本题采用捆绑测试。

::cute-table{tuack}

子任务 n≤n\le 分值
11 1010
22 10210^2 3030
33 10310^3 2020
44 10510^5 1010
55 10610^6
66 2×1072\times 10^7 2020

对于所有数据,4≤n≤2×1074\le n\le2\times10^7。

请注意常数因子对运行效率的影响。