G · Ghost of Tsushima：中文题面

时限 4 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

在按固定顺序编号的环上，有 $n$ 个顶点和 $n$ 条不同的无向边 $e_i=\{i,i+1\}$ ，编号 $n+1$ 视为 $1$ 。当 $n=1$ 时是一条自环；当 $n=2$ 时是两条不同的平行边。

区间 $[l,r]$ 沿编号递增方向从顶点 $l$ 走到 $r$ ： $l<r$ 时覆盖 $l,\ldots,r$ 及边 $e_l,\ldots,e_{r-1}$ ； $l>r$ 时经过 $n$ 后绕回 $1$ ； $l=r$ 时只覆盖一个顶点、不覆盖任何边。即使覆盖所有顶点，区间也只走 $n-1$ 条边，并不是整个环。

若区间 $A$ 包含 $B$ 的所有顶点以及所有边，称 $A$ 包含 $B$ 。一个区间集合 $T$ 合法，当且仅当其中任意两个不同区间都不互相包含；空集也合法。

令 $f(T)$ 为任意一条边被 $T$ 中区间覆盖次数的最大值， $g(T)$ 为任意一个顶点的最大覆盖次数，空集两者都为零。对每个 $k=1,\ldots,n$ ，分别求合法集合中满足 $f(T)\le k$ 的数量，以及满足 $g(T)\le k$ 的数量。两种限制分别统计，不是要求同时成立。答案模 $998244353$ 。

输入、输出与约束 #

$1\le T\le10^6$ 。每组一个 $1\le n\le10^6$ ，保证 $\sum n\le10^6$ 。每组输出两行、每行 $n$ 个整数：第一行第 $k$ 项对应边覆盖限制，第二行第 $k$ 项对应点覆盖限制。

样例 #

输入 1 #

输出 1 #

2
2
7 7
6 7
77 112 117 117
46 99 116 117

样例说明 #

$n=1$ 时只有区间 $[1,1]$ ，合法集合为空集和只含该区间的集合，两行答案均为二。 $n=2$ 时有空集、四个单元素集合，以及 $\{[1,1],[2,2]\}$ 、 $\{[1,2],[2,1]\}$ ，共七个。后一个集合的两区间覆盖相同顶点但不同边，所以互不包含；每条边只覆盖一次、每个点覆盖两次。因此两行分别为 7 7 和 6 7。

整理进度 #

本批材料没有这道题的个人 C++ 文件，因此这里先保留中文题面与样例解释；不把题面整理记作已补题。赛时提交过程与赛后补题记录待补。