详细题解：Ghost of Tsushima 详细题解 - 洛谷专栏

简要题意

有一个 $n$ 个点组成的环，边为 $e_1,e_2,\ldots,e_n$，其中 $e_i$ 连接 $i$ 和 $i+1$（下标循环）。

定义一个环上的区间 $[l,r]$：从点 $l$ 沿顺时针一直走到点 $r$，包含经过的所有点和边；特别地，$l=r$ 时只包含点 $l$，不包含任何边。

如果区间 $A$ 包含了区间 $B$ 的所有点和边，就称 $A$ 包含 $B$；选出若干个区间组成集合 $T$。若其中任意两个不同区间都不存在包含关系，则称 $T$ 合法。空集也合法。

对于一个合法集合 $T$，定义：$f(T)=\max_{\text{边 }e}\{\text{包含边 }e\text{ 的区间数}\}$ 即任意一条边被覆盖次数的最大值；$g(T)=\max_{\text{点 }v}\{\text{包含点 }v\text{ 的区间数}\}$ 即任意一个点被覆盖次数的最大值。

对于每个 $k=1,2,\ldots,n$，分别求：满足 $f(T)\le k$ 的合法集合 $T$ 的数量和满足 $g(T)\le k$ 的合法集合 $T$ 的数量。答案对 $998244353$ 取模。

$\sum n\le 10^6$

前置

反射容斥（reflection principle）解决的标准问题是：

格路问题：从 $(0,a)$ 出发，每步向右上或右下走一格（即 $(x,y) \to (x+1, y\pm 1)$），走 $n$ 步到达 $(n,b)$，不触碰直线 $y=0$ 与 $y=L$ 的方案数。 $$ \sum_{j=-\infty}^{\infty}\binom{n}{\frac{n+b-a}{2}+jL}-\binom{n}{\frac{n-b-a}{2}+jL} $$

可以参考 Hanghang007 - 反射容斥 。默认的话下面的反射容斥走法都是每步朝右上或者右下走。

子问题：从 $(0,2d)$ 出发（$2d \in (0,L)$），走 $2n$ 步回到原高度 $(2n,2d)$ 的路径数量，其中 $d$ 是需要枚举的数。

注意到对于任意一条合法路径 $(0,q_0)\to (1,q_1)\cdots \to (2n,q_{2n}=q_0)$，我们可以做变换 $(0,q_1)\to (1,q_2)\cdots \to (2n-1,q_{2n})\to (2n,q_1)$ 这仍然是一条合法的路径；又因为每一步是往右上/右下走，$q_0$ 和 $q_1$ 的奇偶性不同。这是一个双射，因此所有从 $(0,偶数)$ 走到 $(2n,起点高度)$ 路径个数恰好等于从 $(0,奇数)$ 出发走到 $(2n,起点高度)$ 的路径数量。

那么，设要求的答案为 $S$，那么： $$ \begin{aligned} 2S &=\sum_{2d\in(0,L)}\sum_j \left[ \binom{2n}{n+jL}-\binom{2n}{n+2d+jL} \right]\\ &\quad+\sum_{2d+1\in(0,L)}\sum_j \left[ \binom{2n}{n+jL}-\binom{2n}{n+2d+1+jL} \right]\\ &=\sum_{t=1}^{L-1}\sum_j \left[ \binom{2n}{n+jL}-\binom{2n}{n+t+jL} \right]\\ &=(L-1)\sum_j\binom{2n}{n+jL} -\sum_j\sum_{t=1}^{L-1}\binom{2n}{n+t+jL}. \end{aligned} $$ 其中 $\sum_{j}\sum_{t=1}^{L-1}\binom{2n}{n+t+jL}$ 恰好取遍了不被 $L\not \mid i$ 的所有 $\binom{2n}{n+i}$，因此： $$ \sum_{j}\sum_{t=1}^{L-1}\binom{2n}{n+t+jL}=\sum_{i}\binom{2n}{i}-\sum_{j}\binom{2n}{n+jL} $$ 因此可得 $S=\frac{L}{2}\sum_j\binom{2n}{n+jL} -2^{2n-1}$。

题解

注意到链上时左端点和右端点肯定是按序依次匹配，但由于环上由于存在跨过 $(n,1)$ 边的区间，不一定是这样匹配的。不过我们略微观察，注意到设 $d$ 为跨过 $(n,1)$ 边的区间数量，如果确定了 $d$，合法方案最多就一种：

设 $l_1 < l_2 < \ldots < l_m$ 是左端点序列，$r_1 < r_2 < \ldots < r_m $ 是右端点序列，那么肯定是 $[l_1,r_{1+d}],[l_2,r_{2+d}]\dots[l_{m-d+1},r_1],[l_{m-d+2},r_2]\dots[l_m,r_d]$ 组成的集合 $T$ 才有可能合法。证明略。

什么时候 $T$ 是一个合法的区间集合？那么我们不妨数学化的刻画这个问题：

初值和终值有： $D(0)=D(n)=0$、$Y_1=Y_{2n+1}=0$、$Q_1=Q_{2n+1}=1$。

那么对于一组端点序列和跨过 $(n,1)$ 的区间个数 $d$，合法当且仅当 $0\le d+Y_i\le m$。

• 对于限制 $l_{m-d+i}>r_i$，我们考虑其不合法限制：$l_{m-d+i}\le r_i$，可以推得：

• $P_L(r_i)\ge m-d+i,P_R(r_i)=i\to d+D(r_i) +c_R(r_i)\ge m+1$

• 从反方向来看，若存在位置 $x$ 满足 $d+D(x)+c_R(x)=d+P_L(x)-P_R(x-1)\ge m+1$ ，设 $j=P_R(x-1)+1$，则 $P_L(x)\ge m-d+j$。又因为 $P_L(x)\le m\to j\le d$，所以 $l_{m-d+j}\le x,r_j\ge x$，即 $l_{m-d+j}\le x\le r_j$

• $l_{i}\le r_{i+d}$。这条就是描述左端点的前缀和加上 $d$ 不能小于右端点的数量，等价于：$d+D(r_i)\ge 0$。

那么对于点覆盖和边覆盖，分别可以转化为下列计数问题：

• 固定 $m$，枚举 $d,c_L,c_R$，其中 $0\le d\le m,\sum_{x=1}^n c_L(x)=\sum_{x=1}^n c_R(x)=m.$

• 对于边覆盖，计数满足 $0\le d+D(i)\le k,0\le d+D(i)+c_R(i)\le m$ 的数量。

• 对于点覆盖，计数满足 $0\le d+D(i),0\le d+D(i)+c_R(i)\le \min(m,k)$ 的数量。

注意到如果 $k> m$ 的情况下，任何合法集合 $|T|=m$ 的覆盖次数都小于等于 $m$。因此，重新转化下列问题：

• 对于边覆盖，求出 $|T|\le k$ 的 $T$ 的数量和 $|T|>k,0\le d+D(i)\le k$ 的集合 $T$ 数量之和。
• 对于点覆盖，求出 $|T|\le k$ 的 $T$ 数量和和 $|T|>k,0\le d+D(i),0\le d+D(i)+c_R(i)\le k$ 的集合 $T$ 数量之和。

那么我们分成两部分进行计算。

在下面的问题中，我们所说的枚举 $(c_L,c_R)$ 序列默认是枚举所有满足如下约束的 $(c_L,c_R)$ 序列：

• $c_L(i),c_R(i)\in\{0,1\}$
• $\sum_{i}c_L(i)=\sum_ic_R(i)=m$，其中 $m$ 是我们枚举的区间数量；求不限制区间数的总答案时，还要对 $m=0,1,\ldots,n$ 求和。

2.边覆盖

因为 $\Delta Q_i=Q_i-Q_{i-1}\in\{1,-1\}$，我们可以用反射容斥进行描述。

我们不妨先算只有限制 $0\le 2d+Q_{i} \le 2k+2$ 的序列的贡献，再减去 $m\le k$ 的序列的多算贡献。就相当于这个子问题：

从 $(1,2d+1)$ 开始,走到 $(2n+1,2d+1)$，不能超过 $y=0$ 和 $y=2k+2$ 的方案数，对 $d\in[0,k]$ 求和。（设 $L=2k+4$）

根据前置知识得：$S=\frac{L}{2}\sum_{j}\binom{2n}{n+jL}-2^{2n-1}$。

我们多算了什么？我们任取 $d\in[0,k]$ 和序列 $Q$，若满足 $0\le 2d+Q_i\le 2k+2$ ，就会被多算一次。

因为 $Q$ 序列不好描述区间数量 $m$，我们转而枚举 $d$ 和端点序列 $(c_L,c_R)$ （$m\le k$）进行描述，那么当满足 $0\le d+D_i\le k$ 的时候会在反射容斥里算一次。即对于一个区间数量小于等于 $k$ 的端点序列 $(c_L,c_R)$，恰好在反射容斥里会被算 $(k+1)-(\max D -\min D)$ 次。

我们不妨考察这个 $(c_L,c_R)$ 序列正常对答案的贡献是多少，即看在 $m\le k$ 的时候的合法序列数量。此时的限制为 $0\le d+Y(i)\le m$，那么这个序列会被算 $(m+1)-(\max Y -\min Y)$ 次（因为 $Y$ 首尾都是 $0$，且总共只有 $m$ 次上升和 $m$ 次下降，所以 $\max Y-\min Y\le m$。因此，在 $m\le k$ 时，这些平移区间都非空，所以可以这么算）。也就是说：

• 反射容斥里已经计入了 $k+1-(\max D-\min D)$ 次。

• 实际应该计入 $m+1-(\max Y-\min Y)$ 次。

两者相减，才是我们需要弥补的次数。那么我们在预先计入了反射容斥的答案后这个序列的贡献还需要再减去： $$ (k-m) + \min D -\min Y +\max Y -\max D $$ 次。我们注意到了这个性质：

• $\min Y =\min D$：$\min Y=\min_i(Y_i)=\min_i(D(i),D(i)+c_R(i))=\min D$

那么我们还需要找出 $\max Y$ 和 $\max D$​ 之间的联系，（并没有）注意到我们可以通过构造循环位移来构造。具体地，保持左端点不动，令 $c'_R=(c_R(n),c_R(1),\ldots,c_R(n-1))$，新配置的右端点前缀和为 $P'_R(i)=c_R(n)+P_R(i-1)$。因此 $$ D'(i) =P_L(i)-P'_R(i)=P_L(i)-P_R(i-1)-c_R(n)\\ =D(i)+c_R(i)-c_R(n) =Y_{2i}-c_R(n). $$ 由于 $Y$ 的最大值一定在 $Y_{2i}$ 处取得，且 $D'(0)=D'(n)=0$，所以：$\max D'=\max Y-c_R(n)$，即：

• $\max Y-\max D = (\max D'-\max D)+c_R(n).$

设所有 $(c_L,c_R)$ 构成的集合为 $S$，同时注意到循环右移因为可逆且唯一，所以循环右移是从 $S$ 到 $S$ 的一个双射。那么我们统计所有 $(c_L,c_R)$ 就相当于统计所有 $(c_L,c_R')$，那么重写 $\max D$ 的贡献，即：

• $\sum_{(c_L,c_R')}\max D' = \sum_{(c_L,c_R)}\max D$

根据以上几条性质化简，即为： $$ \sum_{m=0}^{k}\sum_{(c_L,c_R)}(k-m) + \min D -\min Y +\max Y -\max D\\ =\sum_{m=0}^{k}\sum_{(c_L,c_R)}(k-m)+c_R(n)\\ =\sum_{m=0}^{k}(k-m)\binom{n}{m}^2+\binom{n}{m}\binom{n-1}{m-1}= \sum_{m=0}^{k} \left(k-\frac{n-1}{n}m\right)\binom nm^2 $$ 这是因为取 $m$ 个左端点和右端点的方案数各为 $\binom{n}{m}$ 且相互独立；当 $c_R(n)$ 有贡献是只能是 $c_R(n)=1$，那么已经确定了一个右端点，剩下的方案数即 $\binom{n}{m}\binom{n-1}{m-1}$。

那么答案就是两部分相减，即： $$ \boxed{\text{Ans}_{\text{环,边}}(k) = \sum_{m=0}^{k}\left(\frac{n-1}{n}m - k\right)\binom{n}{m}^2 + (k+2)\sum_{j}\binom{2n}{n-2j(k+2)} - 2^{2n-1}} $$

3.点覆盖

限制仅有 $0\le d+Y_i\le k$，限制转移到 $Q$ 序列上相当于 $0\le 2d+Q_{i} \le 2k+1$。

同理，我们先算只有限制 $0\le 2d+Q_i\le 2k+1$ 的序列的贡献，再减去 $m\le k$ 的序列的多算贡献。

从 $(1,2d+1)$ 开始,走到 $(2n+1,2d+1)$，不能超过 $y=0$ 和 $y=2k+1$ 的方案数，对 $d\in[0,k]$ 求和。（设 $L=2k+3$）

同理，根据前置知识， $S=\frac{L}{2}\sum_j\binom{2n}{n+jL}-2^{2n-1}$。

同理，我们枚举 $(c_L,c_R)$，那么这个序列在 $m\le k$ 里产生的合法序列总数是 $(m+1)-(\max Y-\min Y)$；在反射容斥里产生的序列数量为 $(k+1)-(\max Y-\min Y)$。综合来看，这个序列我们还需要减去 $k-m$ 次。那么一共要减去： $$ \sum_{m=0}^{k}(k-m)\binom{n}{m}^2 $$ 那么合起来即： $$ \boxed{Ans_{\text{环,点}}(k)=\sum_{m=0}^{k} (m-k) \binom{n}{m}^2 + \frac{2k+3}{2} \sum_{j=-\infty}^{\infty} \binom{2n}{n + j(2k+3)} - 2^{2n-1}} $$

4.复杂度

注意到：当确定了 $n,k$ 之后， $\binom{2n}{n+j(2k+3)}$ 只会有 $O(\frac{n}{k})$ 项非 $0$，我们只需要计算非 $0$ 项的贡献，那么总复杂度为 $O(\sum_{k=1}^{n}O(\frac{n}{k}))=O(n\log n)$。