Ghost of Tsushima 详细题解

max67 · 2026-05-19 20:49:16 · 个人记录

题解

前排提醒，使用 gpt 阅读效果会更好。

0. 前置知识：反射容斥

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

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

这里要求 n\ge0、L\ge2，且 a,b 是满足 1\le a,b\le L-1 的整数。约定组合数下标不是整数、下标越界，或上标为负时，该项为 0。

注意“不触碰边界”和“不超过边界”不一样。如果允许高度落在闭区间 [0,B] 内，就应将整条路径上移 1 格，转化为不触碰 0,B+2；起点和终点也要一起加 1。

可以参考 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}。

前排提醒，这里面参杂了很多对解题没有帮助的东西，可以选择性略过或者看另一篇题解。

1. 中文题面

有一个 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

一些显然的小性质和约定：

注意到如果两个区间的左端点相同，那么会立刻产生包含关系；因此所有区间的左端点互不相同，所有区间的右端点互不相同。
假设我们选择了一些左端点和一些右端点，我们把这些端点构成的集合叫做端点序列 (L,R)，其中 L 是左端点的集合，R 是右端点的集合，和下面的 (c_L,c_R) 表示的是同一个信息。
我们用 m=|T| 来表示 T 中的区间数量，因为上一个性质，区间的左端点互不相同，因此有 0\le m\le n。
未特别注明时，\sum_j 表示对全部整数 j 求和。

怎么做呢？做环不如先做链。我们先来考虑链上的问题。

2. 链

先只允许 1\le l\le r\le n，即不允许区间跨过边 (n,1)。

2.1 区间集合的端点刻画

直接计数区间不大好算，因为我们不是很好描述区间之间的包含和相交关系。那么我们不如尝试考察端点集合和合法集合 T 的对应关系。

设左端点依次为 l_1<\cdots<l_m。按这个顺序写出各区间对应的右端点 t_1,\ldots,t_m。能感受出来 t 序列是递增的。

证明：若存在 i<j 使 t_i>t_j，由于第二个区间合法，有 l_i<l_j\le t_j<t_i，于是 [l_i,t_i] 包含 [l_j,t_j]，矛盾。因此右端点必须严格递增。

所以，若右端点排序为 r_1<\cdots<r_m，唯一可能的配对是 T=\{[l_i,r_i]:1\le i\le m\}；反过来，只要对于所有区间都满足 l_i\le r_i，加上 l_i 互不相同和 r_i 互不相同的限制，这个配对中的区间就都合法。

若左右端点均严格递增，且 l_i\le r_i，则各区间合法；对任意 i<j，有 l_i<l_j、r_i<r_j，两个区间也不可能相互包含。

这意味着：确定左端点集合与右端点集合（不可重集），在确保 l_i\le r_i 的前提下，区间集合就唯一确定。因此我们只需对端点集合计数。

2.2 前缀和与覆盖次数

先来一些定义：

符号	含义
c_L(i)=[i\text{ 是左端点}]	点 i 是否为某区间的左端点（0/1）
c_R(i)=[i\text{ 是右端点}]	点 i 是否为某区间的右端点（0/1）
P_L(i) = \sum_{j\le i} c_L(j)	前 i 个位置的左端点数
P_R(i) = \sum_{j\le i} c_R(j)	前 i 个位置的右端点数
D(i) = P_L(i) - P_R(i)	未闭合的左端点数

初始有 P_L(0)=P_R(0)=D(0)=0。

覆盖次数公式：

边 (i,i+1) 被覆盖的次数：满足区间的左端点在 [1,i] 且右端点在 [i+1,n] 的区间数量，故 f_T(e_{(i,i+1)}) = P_L(i) - P_R(i) = D(i)
点 i 被覆盖的次数：满足区间的左端点在 [1,i] 且右端点在 [i,n] 的区间数量，故 g_T(i) = P_L(i) - P_R(i-1) = D(i) + c_R(i)

还有一些函数本身的约束：

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

c_L(i),c_R(i)\in\{0,1\}

下文所说的枚举 Y 序列或者枚举 Q 序列本质上还是在枚举 (c_L,c_R) 序列并依此计算出 Y 序列和 Q 序列；下文写的 \sum_{(c_L,c_R)} 的意思也是枚举 (c_L,c_R) 序列。不写 m 的话默认 m 是固定的一个数。

2.3 两个子问题的形式化

紫玛利，链上的问题等价于统计如下序列的个数：

对 m=0,1,\ldots,n 求和，并枚举左右端点各有 m 个的 c_L,c_R。
边覆盖小于等于 k ：枚举 c_L,c_R，计数满足 0\le D(i)\le k 的个数。
点覆盖小于等于 k ：枚举 c_L,c_R，计数满足 0\le D(i),0\le D(i)+c_R(i)\le k 的个数。

3. 链上的边覆盖

3.1 方法一：暴力计算！

我们发现，如果一个点同时是左端点和右端点或者这个点上没有左端点和右端点，那么这个点总不会对 D 的值产生任何影响，在去掉这些点后，这样的话每个端点要么是左端点要么是右端点，就可以进行反射容斥计数：（c0\le i\le\min(m,n-m)）

设选了m-i 个点同时是左端点和右端点；i 个点只有左端点，i 个点只有右端点；剩下 n-m-i 个点没有端点。那么这部分方案数是 \binom{n}{2i}\binom{n-2i}{m-i}。
然后敲定哪些点是左端点/右端点这等价于如下的一个子问题：

在 2i 个位置上放 i 个 +1 和 i 个 -1，使得前缀和总是在 [0,k] 内。这等价于这个反射容斥：

从 (0,0) 走到 (2i,0)，不越过 y=0 和 y=k 的方案数：

由反射容斥可得，式子为（设 L=k+2）： \sum_{j} \left[\binom{2i}{i+jL} - \binom{2i}{i-1+jL}\right]

即：

\sum_{m=0}^{n}\sum_{i=0}^{\min(m,n-m)}\binom{n}{2i}\binom{n-2i}{m-i}\sum_j\left[\binom{2i}{i+jL}-\binom{2i}{i-1+jL}\right]

先计算 \sum_m \sum_i \binom{n}{2i}\binom{n-2i}{m-i}\sum_j \binom{2i}{i+jL}，因为我们想要把和 i 有关的项从二项式的上面位置挪到下面位置方便做变换，因此注意到：\binom{n}{2i}\binom{n-2i}{m-i}\binom{2i}{i+jL} = \binom{n}{m-jL}\binom{m-jL}{i-jL}\binom{n-m+jL}{n-m-i}

我们再重写一下式子，发现形成了范德蒙德卷积的形式：

\sum_j\sum_m\binom{n}{m-jL}\sum_i\binom{m-jL}{i-jL}\binom{n-m+jL}{n-m-i}\\ =\sum_j\sum_m\binom{n}{m-jL}\binom{n}{n-m-jL}=\sum_j\binom{2n}{n-2jL}

同理处理 \sum_m \sum_i \binom{n}{2i}\binom{n-2i}{m-i}\sum_j \binom{2i}{i-1+jL} 项，因为有：\binom{n}{2i}\binom{n-2i}{m-i}\binom{2i}{i-1+jL}=\binom{n}{m+1-jL}\binom{m+1-jL}{m-i}\binom{n-m-1+jL}{n-m-i}，同样可以推得其为 \sum_j\binom{2n}{n+2-2jL}。

最终答案： \boxed{\text{Ans}_{\text{链,边}}(k) = \sum_{j=-\infty}^{+\infty}\left[\binom{2n}{n-2j(k+2)}-\binom{2n}{n+2-2j(k+2)}\right]}

3.2 方法二：反射容斥

因为 D(i+1)-D(i)\in\{-1,0,1\}，与通常的卡特兰数形式不对应，因此我们渴望变换 D 序列来构造成每步都是 (1,\pm 1) 的序列。

受到求点覆盖次数 D+c_R(i) 的启发：我们需要把 c_L(i) 和 c_R(i) 拆成两步来计算，即设：

符号	含义
Y_{2i} = D(i)+c_R(i)	第 i 个点的覆盖次数
Y_{2i+1}=D(i)	第 i 条边的覆盖次数

也就是说，每个点先加入左端点，再移除右端点。补上 Y_1=D(0)=0，则对于 1\le i\le n，有：

Y_{2i}-Y_{2i-1}=c_L(i),\qquad Y_{2i+1}-Y_{2i}=-c_R(i).

因此 Y_{2i} 是点状态，Y_{2i+1} 是处理完第 i 个点后的边状态。

约束：从 0\le D(i)\le k 可以推得：0\le Y_{2i+1}\le k，0\le Y_{2i}\le k+1。

初值、终值：Y_{1}=Y_{2n+1}=0。

还差一点就达到了我们的预期。我们想让每一步都是往上走或者往下走，而不是根据奇偶讨论，再巧妙运用一下代数变形：f(x)=1-2x 可以把 \{0,1\} 变换到 \{-1,1\}。因此我们设：

符号	含义
Q_{2i}=2(D(i)+c_R(i))	2Y_{2i}
Q_{2i+1}=2D(i)+1	2Y_{2i+1}+1

Q_{2i}-Q_{2i-1}=2c_L(i)-1,Q_{2i+1}-Q_{2i}=1-2c_R(i)

约束：Q_{2i} 是偶数，Q_{2i+1} 是奇数

0\le Q_{2i}\le 2k+2
0\le Q_{2i+1}\le 2k+1,2\nmid Q_{2i+1}\iff 0\le Q_{2i+1}\le 2k+2
即 0\le Q_i\le 2k+2。

初值：Q_1=Q_{2n+1}=1。

四种局部情况如下：

(c_L(i),c_R(i))	D 的变化	Q 的两步
(0,0)	0	-1,+1
(1,0)	+1	+1,+1
(0,1)	-1	-1,-1
(1,1)	0	+1,-1

这也说明：只看 D，无法区分「没有端点」与「左右端点同时出现」；插入中间状态 Y_{2i-1} 后，两者便被区分开了。

同时，因为我们总是在枚举 (c_L,c_R) 再通过 D 序列统计合法个数，那么我们可以变为枚举 (c_L,c_R) 再根据 Q 序列计算合法个数；同时又因为可以从 Q 序列推出 (c_L,c_R)，因而我们只需要对合法的 Q 序列进行计数，那么问题变为：

从 (1, Q_1=1) 走到 (2n+1, Q_{2n+1}=1)，不超过 y=0 和 y=2k+2。

由反射容斥：

\boxed{\text{Ans}_{\text{链,边}}(k) = \sum_{j} \left[\binom{2n}{n+j(2k+4)}-\binom{2n}{n-2+j(2k+4)}\right]}

4. 链上的点覆盖

方法一是边覆盖特有的性质，而在链上我们需要同时依靠 D 序列和 c_R 来描述点覆盖的情况。因而我们模仿之前的方法二。约束为：

0\le D_i,0\le D(i)+c_R(i)\le k
即 0\le Y_{i}\le k （注意 Y_{2i} 的上界从 k+1 降为 k，因为点覆盖也算上右端点本身。）

在 Q 序列下有：

0\le Q_{2i+1}\le 2k+1\\ 0\le Q_{2i}\le 2k,2|Q_{2i}\iff 0\le Q_{2i}\le 2k+1
即 0\le Q_i\le 2k+1。

这就等价于下面这个问题：

从 (1,Q_{1}=1) 走到 (2n+1,Q_{2n+1}=1)，不能超过 y=0 和 y=2k+1 的方案数。

由反射容斥：

\boxed{\text{Ans}_{\text{链,点}}(k) = \sum_{j}\left[\binom{2n}{n+j(2k+3)}-\binom{2n}{n+2+j(2k+3)}\right]}

5. 环上的关键转化

相比链又复杂很多，同样的，先端点的选取再考虑这些端点能组成哪些区间。不过根据链上的情况，我们相信端点序列应该依然是按照端点递增排列后的某种顺序进行组合的。

5.1 跨边匹配

在环上一个端点集合应该对应着不只一种匹配方案，但链上确实只有一种匹配方案。那么我们不妨断环为链，在边 (n,1) 处切开环，设 d 是跨过这条边的区间数。我们大胆猜测，确定了端点集合和 d 之后，匹配最多只有一种。

定理：将左端点升序排为 l_1<\dots<l_m，右端点升序排为 r_1<\dots<r_m。则要求跨 (n,1) 的 d 个区间必为 [l_{m-d+1},r_1],[l_{m-d+2},r_2],\dots,[l_m,r_d]；剩余 m-d 个不跨的区间必为 [l_1,r_{d+1}],\dots,[l_{m-d},r_m]。证明如下：（1\le i\le d）

假如 l_{m-d+i} 所在的区间并未跨过 (n,1)，那么 l_{m-d+i} 所在的区间被 [l_{m-d+i},n] 包含，再依据鸽巢原理，由于至少有 d 个左端点跨过了 (n,1) 边，而左端点大于 l_{m-d+i} 的个数不到 d 个，因此在 l_1,l_2...l_{m-d+i-1} 之中必然至少有一个点所在的区间跨过了 (n,1)，设这个点为 l_p。那么 l_p 所在的区间肯定包含 [l_p,n]，可以推出 l_p 所在的区间包含 l_{m-d+i} 所在的区间，矛盾。因此这说明 l_{m-d+1}...l_{m} 都跨过了 (n,1)；r 序列同理

因为 l_{m-d+1}<l_{m-d+2}\ldots <l_m,r_1<r_2...<r_m，那么只能依次匹配否则会导出包含关系。最后剩下了 l_1\ldots l_{m-d} 的左端点和 r_{d+1}\dots r_m，依据链上的情况，只能依次匹配 [l_1,r_{d+1}],[l_2,r_{d+2}]\ldots

接下来考虑什么时候这个匹配存在，即其合法性。

5.2 合法性条件

显然，对于我们强制要求跨过 (n,1) 边的区间 [l_{m-d+i},r_i]，必须有 l_{m-d+i}>r_i，再加上原本链上存在的约束，那么对于一个端点序列和 d，对应一个合法的合法集合 T 当且仅当满足以下约束：

l_i \le r_{i+d},i\in[1,m-d]

再来证明满足上面约束的端点集合和 d 确实是一个合法方案：把环周期性地展开到数轴上，令 l_{i+m}=l_i+n、r_{i+m}=r_i+n。所有区间便统一写成 [l_i,r_{i+d}]，并且有 l_i\le r_{i+d}<l_i+n，即区间合法且长度不超过 n；另一方面，由右端点的循环配对顺序，有 r_1<r_2<\cdots<r_m<r_1+n。因此，对于任意 i<j，都有 r_i<r_j<r_i+n。

现在分别排除两种包含关系：（i<j）

第 i 个区间包含第 j 个区间。从 l_i 处展开环，第 j 个区间的左端点是 l_j>l_i，其右端点为 r_{j+d}>r_{i+d}，因此它不可能被包含。

第 j 个区间包含第 i 个区间。从 l_j 处展开环，第 i 个区间应表示为 [l_i+n,r_{i+d}+n]。但 r_{i+d}+n>r_{j+d}，因此它同样不可能被包含。

5.3 模型刻画

再回忆一遍符号，设 d 表示跨过 (n,1) 边的区间数量：

符号	含义
c_L(i)	点 i 是否为某区间的左端点（0/1）
c_R(i)	点 i 是否为某区间的右端点（0/1）
P_L(i) = \sum_{j\le i} c_L(j)	前 i 个位置的左端点数
P_R(i) = \sum_{j\le i} c_R(j)	前 i 个位置的右端点数
D(i) = P_L(i) - P_R(i)	左右端点前缀计数之差
Y_{2i} = D(i)+c_R(i)	前 i 个点的左端点和减去前 i-1 个点的右端点和
Y_{2i+1}=D(i)	前 i 个点的左端点和减去前 i 个点的右端点和
Q_{2i}=2(D(i)+c_R(i))	2Y_{2i}
Q_{2i+1}=2D(i)+1	2Y_{2i+1}+1

我们同样的尝试用 D 序列去描述上面的问题：

对于限制 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)\ge m\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
那么即 d+D(r_i)+c_R(i)\le m 确实是 l_{m-d+i}> r_i 的充要条件。

因此全部配对合法，当且仅当

\boxed{ d+D(x)\ge0,\qquad d+D(x)+c_R(x)\le m. }

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

固定 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 数量之和。

6 计数 |T|=m 的合法集合 T 数量

（实际上这部分贡献会被消掉，求不求无所谓qaq）

按照上面的分析，去掉 k 的限制后，一个合法的集合 T 恰好要满足 0\le d+D(i),0\le d+ D(i)+c_R(i)\le m，即 0\le d+Y_{2i}\le m,0\le d+Y_{2i+1}\le d+Y_{2i}\le m。即：

0\le d+Y_i\le m

这个形式就漂亮很多了，我们考虑对这个计数。

6.1 模型计数

我们考虑我们是如何计数合法集合 T 的：

第一步，从 n 个点里面选出 m 个左端点，从 n 个点里面选出 m 个右端点。
第二步，对于他们产生的前缀和序列（Y_{i} 序列），我们把他上下平移（改变 d 的值），如果能塞进 y=0 和 y=m 的限制内，即 0\le d+Y_i\le m，那么这就是一个合法的方案。

设 \max_i(Y_i)-\min_i(Y_i)=A（即振幅），实际上，在第二步中的上下平移的方案数是 \max(0,m+1-A)。注意到 T 里一共是 m 个区间，因此闭合的 Y 路径总上升量和总下降量都恰好为 m，可以看出 A\le m，那么贡献系数可以写成： m+1-A。那么我们把其拆成两部分进行计算：

式子=\sum_{Y}\max(Y)-\min(Y)\\ =\sum_{Y}\sum_{h}[\max(Y)\ge h]+[\min(Y)\le -h]

这种形式很熟悉啊，看上去就很像卡特兰数，但还是那个问题：Y 的形式和卡特兰数并不匹配，而转成 Q 序列的话我们发现我们没办法限制 |T|=m。

这题肯定就不能在这里结束，我们决定做一个违背祖宗的决定：直接对 Y 序列进行反射容斥。

下文我们分别计算 \sum_{Y}\sum_{h}[\max(Y)\ge h] 和 \sum_{Y}\sum_{h}[\min(Y)\le -h]。

6.3 \sum_{Y}\sum_{h}[\min(Y)\le -h]。

找到第一个 Y_p=-h 的位置 p，显然因为 Y_{2i}=D(i)+c_R(i)\ge Y_{2i+1}=D(i)，p 总是一个奇数。我们翻转所有位置 p 后的路径，我们考察什么东西不会随着位置 p 的变化而变化：

设 \Delta Y_i=Y_i-Y_{i-1}，经过一些观察，我们注意 \Delta Y_i= 1 的数量从 m 变为了 m-h，\Delta Y_i=-1 的数量从 m 变为了 m+h。

假设在反射前在 p 前有 u 个 \Delta Y 的取值为 +1，p 前有 d 个 \Delta Y 的取值 -1；在 p 后有 a 个 +1，在 p 后有 b 个 -1。那么有关系：
d-u=h,u+a=d+b=m
那么可以推出反射后总 +1 的个数为 u+b=m-h，反射后总 -1 的个数为 d+a=m+h。

不过，这些 \Delta Y=+1 的东西能放在哪些位置上呢？我们注意到在原先的方案里，\Delta Y_{2i}\in\{0,1\},\Delta Y_{2i-1}\in \{0,-1\}，在翻转后的方案里，如果 i>p，那么 \Delta Y_{2i}\in\{0,-1\},\Delta Y_{2i+1}\in \{0,1\}，因为 p 是个奇数，我们发现翻转并没有改变 \Delta Y_{i}\in \{0,-1\} 和 \Delta Y_i\in \{0,1\} 的数量。
那么我们需要枚举哪些位置是 \Delta Y_i\in\{0,-1\} 吗？不需要，假设我们已经按某种顺序确定了 n 个 \Delta Y_i\in\{0,-1\} 的取值和 n 个 \Delta Y_i\in\{0,1\} 的取值，我们可以按照把这 2n 个取值以此放进不翻转 Y 序列里面来推出 p（因为翻不翻转序列 Y 不会改变 p 位置前的信息，所以可以据此推出 p）然后再翻转 p 后的序列就能求出所有 \Delta Y_i 的位置，再把取值放进去。
那么计数翻转之后的方案数：我们往 n 个 \Delta Y_i\in\{0,1\} 的位置里面选出 m-h 个位置赋值为 1，从剩下 n 个 \Delta Y_i\in{0,-1} 的位置里选出 m+h 个位置赋值为 -1 ，也即 \binom{n}{m+h}\binom{n}{m-h}。

6.4 \sum_{Y}\sum_{h}[\max(Y)\ge h]。

同理，在反射后 A 的总个数变成了 n-1 个，B 的总个数变成了 n+1 个，其他不变，那么方案数即为 \binom{n+1}{m+h}\binom{n-1}{m-h}。

6.5 求和

\sum_{h\ge 1} \binom{n}{m+h}\binom{n}{m-h}+\binom{n+1}{m+h}\binom{n-1}{m-h}\\

我们把后面一项展开得和前面的像一点。具体地，把组合数拆开，再把剩下的项合并：
\begin{aligned} \binom{n+1}{m+h}\binom{n-1}{m-h} ={}& \binom n{m+h}\binom n{m-h}\\ &-\binom n{m+h}\binom{n-1}{m-h-1}\\ &+\binom n{m+h-1}\binom{n-1}{m-h}. \end{aligned}
分开求和，我们发现后两项能消掉一部分：
\begin{aligned} &-\sum_{h\ge1}\binom n{m+h}\binom{n-1}{m-h-1} +\sum_{h\ge1}\binom n{m+h-1}\binom{n-1}{m-h}\\ ={}& -\sum_{h\ge1}\binom n{m+h}\binom{n-1}{m-h-1} +\sum_{h\ge0}\binom n{m+h}\binom{n-1}{m-h-1}\\ ={}&\binom nm\binom{n-1}{m-1}. \end{aligned}
所以振幅总和为
2\sum_{h\ge1}\binom n{m+h}\binom n{m-h} +\binom nm\binom{n-1}{m-1}.
对于前面这一项，用范德蒙德卷积，有
\sum_{h\in\mathbb Z}\binom n{m+h}\binom n{m-h} =\binom{2n}{2m}.
正负 h 的贡献相同，去掉 h=0 的项，就得到
2\sum_{h\ge1}\binom n{m+h}\binom n{m-h} =\binom{2n}{2m}-\binom nm^2.

6.6 答案

显而易见，就是：

\boxed{(m+2)\binom{n}{m}\binom{n}{m}-\binom{n}{m}\binom{n-1}{m-1}-\binom{2n}{2m}}

7. 环上的边覆盖

再来复习一遍符号：

符号	含义
c_L(i)	点 i 是否为某区间的左端点（0/1）
c_R(i)	点 i 是否为某区间的右端点（0/1）
P_L(i) = \sum_{j\le i} c_L(j)	前 i 个位置的左端点数
P_R(i) = \sum_{j\le i} c_R(j)	前 i 个位置的右端点数
D(i) = P_L(i) - P_R(i)	未闭合的左端点数
Y_{2i} = D(i)+c_R(i)	前 i 个点的左端点和减去前 i-1 个点的右端点和
Y_{2i+1}=D(i)	前 i 个点的左端点和减去前 i 个点的右端点和
Q_{2i}=Q_{2i-1}+2c_L(i)-1	2Y_{2i}
Q_{2i+1}=Q_{2i}+1-2c_R(i)	2Y_{2i+1}+1

7.1 m \le k

就是 |T|\le k 的方案数：

\sum_{m=0}^{k}(m+2)\binom{n}{m}\binom{n}{m}-\binom{n}{m}\binom{n-1}{m-1}-\binom{2n}{2m}

7.2 m\ge k+1 直接计算

我们选择用 D 序列来计数。依据上文推导，限制条件有且仅有：

0\le d+D(i)\le k

根据链的方法同样开始暴算。同样的，我们枚举有 d 个区间跨过了 (n,1)，目前有 m 个端点，有 m-i 个点既是左端点又是右端点，i 个点只有左端点，i 个点只有右端点。那么就是：（0\le i\le\min(m,n-m)）

\sum_{m\ge k+1}\sum_{i}\sum_{d}\binom n{2i}\binom{n-2i}{m-i}[从 (0,d) 走到 (2i,d) 并且不能穿过 y=0 和 y=k 的方案数]

对于 [] 里的式子，我们算一下这个子问题的解：

问题：不能碰到 y=0 和 y=L，起点可以在 (0,a) -开始（a\in(0,L),a自己选）走到 (n,a) 的方案数之和。

格路问题：从 (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}

那么上面的式子就是：（设 L=k+2）
\begin{aligned} &\sum_{a=1}^{L-1}\sum_j \left[\binom{2s}{s+jL}-\binom{2s}{s-a+jL}\right]\\ ={}&(L-1)\sum_j\binom{2s}{s+jL} -\sum_j\sum_{a=1}^{L-1}\binom{2s}{s-a+jL}\\ ={}&L\sum_j\binom{2s}{s+jL}-2^{2s}. \end{aligned}

将原路径整体上移 1 格，设 L=k+2，再代入 s=i，那么我们要求的式子就是

\sum_{m=k+1}^{n}\sum_{i=0}^{\min(m,n-m)} \binom n{2i}\binom{n-2i}{m-i} \left[L\sum_j\binom{2i}{i-jL}-2^{2i}\right].

设

A=L\sum_{m=k+1}^{n}\sum_{i=0}^{\min(m,n-m)} \binom n{2i}\binom{n-2i}{m-i}\sum_j\binom{2i}{i-jL},

B=\sum_{m=k+1}^{n}\sum_{i=0}^{\min(m,n-m)} \binom n{2i}\binom{n-2i}{m-i}2^{2i}.

我们分别计算 A 和 B。

对于 A，使用链上的相同变换与范德蒙德卷积，有：

\begin{aligned} A &=L\sum_j\sum_{m=k+1}^{n} \binom n{m-jL}\binom n{m+jL}\\ &=L\sum_j\binom{2n}{n-2jL} -L\sum_{m=0}^{k}\sum_j \binom n{m-jL}\binom n{m+jL}\\ &=L\sum_j\binom{2n}{n-2jL} -L\sum_{m=0}^{k}\binom nm^2. \end{aligned}
最后一步是因为 m\le k<L：只要 j\ne0，m-jL 与 m+jL 中必有一个为负数，因此只剩 j=0。

对于 B，我们考虑这个式子的组合意义：

构造一个组合模型：从 n 对不同的鞋子（共 2n 只）中选出 2m 只鞋子，方案数是 \binom{2n}{2m}。

由于总数 2m 为偶数，只选中一只的鞋子对数也必为偶数，设为 2i。

从 n 对鞋子中选出这 2i 对，每对只选一只，先有 \binom n{2i} 种。

对每一对决定选左脚还是右脚，有 2^{2i} 种。

剩下还要选 m-i 对完整的鞋子，有 \binom{n-2i}{m-i} 种。

因此固定 m 时，
\sum_{i=0}^{\min(m,n-m)} \binom n{2i}\binom{n-2i}{m-i}2^{2i} =\binom{2n}{2m}.
最后还要对 m 求和，所以 B=\sum_{m=k+1}^{n}\binom{2n}{2m}。

于是 m>k 的答案为

(k+2)\sum_j\binom{2n}{n-2j(k+2)} -\sum_{m=k+1}^{n}\binom{2n}{2m} -(k+2)\sum_{m=0}^{k}\binom nm^2.

7.3 m\ge k+1 反射容斥

参照链的方法，限制即 0\le 2d+Q_{i} \le 2k+2。

直接算的话是个子问题，不过会算上一些不合法的情况：

从 (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

注意到：枚举区间个数 m：对于一个路径 D_i，因为 \min_i(Y_i)=\min_i(D_i,D_i+c_R(i))=\min_i D_i，且因为对称性，\sum_{D}\max_i(D_i)=-\sum_{D}\min_i(D_i)，因此：（结合 6.3 节）
\sum_{(c_L,c_R)}\max_i(D_i)-\min_i(D_i)=-2\sum_{(c_L,c_R)}\min_i(D_i)\\ =-2\sum_{Y}\min_i(Y_i)=2\binom{n}{m-h}\binom{n}{m+h}=\binom{2n}{2m}-\binom{n}{m}^2

因此应该被减去的个数就是：\sum_{m=0}^{k}\left[(k+2)\binom{n}{m}^2-\binom{2n}{2m}\right]。最后两者相加即可。

7.4 推导化简

因为有 \min Y=\min D，实际上我们需要减去的只是：

\sum_{(c_L,c_R)}(k-m)+\max Y-\max 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)。因此

\begin{aligned} 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). \end{aligned}

由于 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_{c_L,c_R}(\max Y-\max D) =\sum_{c_L,c_R}c_R(n)=\binom nm\binom{n-1}{m-1}

那么需要减去的贡献即为：(k-m)\binom nm^2 + \binom nm\binom{n-1}{m-1}。

7.5 答案

合并 m\le k 和 m>k 的情况，并化简 \sum_{m}\binom{2n}{2m}=2^{2n-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}}

8. 环上的点覆盖

8.1 m\le k

就是 |T|\le k 的方案数：

\sum_{m=0}^{k}(m+2)\binom{n}{m}\binom{n}{m}-\binom{n}{m}\binom{n-1}{m-1}-\binom{2n}{2m}

8.2 m>k

限制即 0\le d+Y_i\le k。参照链的方法，我们设：

限制即 0\le 2d+Q_{i} \le 2k+1。

直接算的话是个子问题，不过会算上一些不合法的情况：

从 (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}。

同理，我们任取 d\in[0,k] 且满足 0\le 2d+Q_i\le 2k+1 的限制合法，那么这就是一个被重复计入的情况。

我们重新回到序列 Y 上考虑问题。此时在 Y 上的限制就是 0\le d+Y_i\le k。与 |T|=m 的推导类似，对于一条 Y_i 路径，当其区间数量小于等于 k 的时候，恰好被算了 (k+1)-(\max_i(Y_i)-\min_i(Y_i)) 次，减去即可：

\sum_{m=0}^{k}\left[(k+2)(\binom{n}{m})^2-\binom{n}{m}\binom{n-1}{m-1}-\binom{2n}{2m}\right]\\

同第 7.4 节，其实这里也可以直接消去振幅的贡献。每个端点配置实际应该计入 m+1-(\max Y-\min Y) 次，所以在 S 的基础上应加上的修正量恰好是

\bigl(m+1-(\max Y-\min Y)\bigr) -\bigl(k+1-(\max Y-\min Y)\bigr) =m-k.

因此全部修正量为 \sum_{m=0}^{k}(m-k)\binom nm^2。采用这个直接修正的式子后，同样不用再额外加第 8.1 节。

8.3 答案

同理，有：

\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}}

9. 另解：矩阵法

结尾再给一个暴力计算方法。由 AI 提供。我觉得应该有人类能这么算出来。

由于篇幅关系，下面只详细演示点覆盖问题的解法。我们从前面已经得到的约束出发，直接计算所有合法集合的答案。

大概思路就是：

我们暴力地把转移写成 dp 矩阵的形式。由于需要对所有起点求和，这就相当于求矩阵的 n 次幂的对角线元素之和。如果你学过线性代数的话，这玩意就是矩阵的迹。
特征值不好直接求啊，不过可以把它们一起放进 \det(I-zA)。取个对数，再求个导，就能与 \operatorname{tr}(A^n) 建立联系。
由于转移的性质，矩阵只有主对角线及其相邻两条对角线可能非零，因此行列式可以用二阶递推求出。再设一个中间变元 u，把特征根和 z 一起表示出来。
最后用拉格朗日反演提取系数。不过这次先把需要相减的贡献合并，能消掉的部分就不用算了。

下面固定 n\ge1、1\le k\le n。约定下标越界的组合数为 0，\sum_{j\in\mathbb Z} 表示对全部整数 j 求和。

9.1 问题描述与转移矩阵

先回忆一下已知约束。左右端点分别用 c_L,c_R 表示，每个位置的取值都是 0 或 1，左右端点总数都为 m。仍然记

D(i)=P_L(i)-P_R(i),\qquad Y_1=0,

Y_{2i}=D(i)+c_R(i),\qquad Y_{2i+1}=D(i) \qquad(1\le i\le n).

$$ 0\le d+Y_j\le m \qquad(1\le j\le 2n+1). $$ 再加上点覆盖不超过 $k$ 的限制，就变成 $$ \boxed{0\le d+Y_j\le \min(m,k).} $$ 因此我们先解决一个统一的子问题： > 给定高度上界 $h$，统计满足 $0\le d+Y_j\le h$ 的端点配置与平移量 $d$。每放一个左端点，就给权重乘上 $y$，这样一个包含 $m$ 个左端点的配置，权重就是 $y^m$。这里先不要求 $h\le m$，所以这个子问题本身可能计入不合法的配对。等提取 $y^m$ 的系数时，我们再把 $h$ 取成 $\min(m,k)$。我们以序列 $D$ 的视角来看，也就是对每个点讨论其是否放左端点、是否放右端点。建一张有 $h+1$ 个点的图，标号为 $0,1,\ldots,h$，标号表示当前的高度 $d+D$。假设现在走到标号为 $i$ 的点，当前的权重积为 $x$。在处理环上的下一个点时，先加入左端点，再移除右端点，因此中间的点覆盖状态是 $i+c_L$。在 $i<h$ 时，分类讨论： - 没有左端点和右端点，转移到 $i$，贡献为 $x$。 - 有左端点，没有右端点，转移到 $i+1$，贡献为 $yx$。 - 没有左端点，有右端点，转移到 $i-1$，贡献为 $x$。 - 有左端点和右端点，转移到 $i$，贡献为 $yx$。在 $i=h$ 时，只能保留下面两种转移： - 没有左端点和右端点，仍然停在 $h$，贡献为 $x$。 - 没有左端点，有右端点，转移到 $h-1$，贡献为 $x$。为什么最上面的点不能同时放左右端点？虽然最后又回到了 $h$，但加入左端点后，中间状态会先达到 $h+1$，已经超过了点覆盖的限制。所有转移都只保留目标状态在 $[0,h]$ 内的情况，特别地，状态 $0$ 不能向下走。我们把转移写成矩阵的形式，设为 $A_h(y)$： $$ A_h(y)= \begin{pmatrix} 1+y & y & 0 & \cdots & 0\\ 1 & 1+y & y & \cdots & 0\\ 0 & 1 & 1+y & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & y\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}. $$ 这是一个 $(h+1)\times(h+1)$ 的矩阵。更准确地说，主对角线上除最后一项为 $1$ 外，其余都是 $1+y$；上对角线为 $y$，下对角线为 $1$。当 $h=0$ 时，直接取 $A_0(y)=(1)$。对于 $(A_h(y)^n)_{i,j}$，其组合意义就是从状态 $i$ 出发，走 $n$ 次到达状态 $j$ 的所有方案的权重之和。我们需要从某个 $d$ 出发，走完 $n$ 个点后回到 $d$。首尾高度相同，恰好保证左右端点总数相等；再对所有起点求和，就得到 $$ F_h(y) := \sum_{i=0}^{h}(A_h(y)^n)_{i,i} = \operatorname{tr}(A_h(y)^n). $$ 于是，$[y^m]F_h(y)$ 统计的就是：左右端点各有 $m$ 个，并且整个 $d+Y$ 序列都在 $[0,h]$ 内的方案数。 ##### 9.2 先把需要相减的贡献合并按照上面的分析，答案可以直接写成 $$ \operatorname{Ans}_{\mathrm p}(k) = \sum_{m=0}^{n}[y^m]F_{\min(m,k)}(y). $$ 不过这样每个 $m$ 都对应一个矩阵，看上去不大好算。我们不妨先统一按上界 $k$ 计算，再修正 $m\le k$ 的部分。注意到 $F_k(y)$ 是次数不超过 $n$ 的多项式，因为每一步最多放一个左端点。因此把所有 $m$ 的系数加起来，就是令 $y=1$： $$ \sum_{m=0}^{n}[y^m]F_k(y)=F_k(1). $$ 那么答案可以改写成 $$ \boxed{ \operatorname{Ans}_{\mathrm p}(k) = F_k(1) + \sum_{m=0}^{k}[y^m]\bigl(F_m(y)-F_k(y)\bigr). } $$ 这个式子的意思是： - 当 $m>k$ 时，本来就应该按上界 $k$ 计算，不用修改。 - 当 $m\le k$ 时，先减去按上界 $k$ 计算的部分，再加上按上界 $m$ 计算的合法部分。（并没有）注意到我们不一定要把这两个部分分别算出来。既然最后需要相减，不如一开始就对着差值计算，看看能不能消掉一些东西。下面只剩两个任务：计算宽松总数 $F_k(1)$，以及修正量 $[y^m](F_m-F_k)$。 ##### 9.3 迹与行列式的关系注意到引理： $$ \sum_{r=1}^{\infty}\operatorname{tr}(A^r)z^r = -z\frac{d}{dz}\log\det(I-zA). $$ > 证明如下。设 $A$ 是一个 $q$ 阶矩阵，特征值为 $\lambda_1,\ldots,\lambda_q$，按重数计算。那么 > > $$ > \det(I-zA)=\prod_{i=1}^{q}(1-z\lambda_i). > $$ > > 因为我们想要求和而不是求积，所以套个 $\log$： > > $$ > \log\det(I-zA) > = > \sum_{i=1}^{q}\log(1-z\lambda_i). > $$ > > 再求个导： > > $$ > \frac{d}{dz}\log\det(I-zA) > = > \sum_{i=1}^{q}\frac{-\lambda_i}{1-z\lambda_i}. > $$ > > 看起来这很像等比数列求和，我们乘上 $-z$ 再展开： > > $$ > \begin{aligned} > -z\frac{d}{dz}\log\det(I-zA) > &= > \sum_{i=1}^{q}\frac{z\lambda_i}{1-z\lambda_i}\\ > &= > \sum_{r=1}^{\infty} > \left(\sum_{i=1}^{q}\lambda_i^r\right)z^r\\ > &= > \sum_{r=1}^{\infty}\operatorname{tr}(A^r)z^r. > \end{aligned} > $$ 下面设 $$ M_h(z,y)=I-zA_h(y), \qquad \Delta_h(z,y)=\det M_h(z,y). $$ 提取 $z^n$ 的系数，可以把 $z\,d/dz$ 去掉： $$ \boxed{F_h(y)=-n[z^n]\log\Delta_h(z,y).} $$ 这里乘上 $n$，是因为对 $z^n$ 求导后再乘 $z$，系数会变为原来的 $n$ 倍。我们显式写出 $M_h$： $$ M_h= \begin{pmatrix} 1-z(1+y) & -zy & 0 & \cdots & 0\\ -z & 1-z(1+y) & -zy & \cdots & 0\\ 0 & -z & 1-z(1+y) & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & -zy\\ 0 & \cdots & 0 & -z & 1-z \end{pmatrix}. $$ ##### 9.4 行列式的递推考虑递推求出 $M_h$ 的行列式。先去掉最后一格的特殊性，设 $P_i$ 是下面这种 $i$ 阶三对角矩阵的行列式：主对角线全部为 $1-z(1+y)$，上对角线为 $-zy$，下对角线为 $-z$。按最后一行展开，就有 $$ \begin{aligned} P_0&=1,\\ P_1&=1-z(1+y),\\ P_i&=(1-z(1+y))P_{i-1}-z^2yP_{i-2} \qquad(i\ge2). \end{aligned} $$ $P_0=1$ 是空行列式的约定。对于原来的矩阵，最后一个对角元变成了 $1-z$，因此当 $h\ge1$ 时， $$ \Delta_h=(1-z)P_h-z^2yP_{h-1}. $$ 利用 $P_i$ 的递推，还可以写成一个更方便的形式： $$ \boxed{\Delta_h=P_{h+1}+zyP_h.} $$ 这个式子在 $h=0$ 时也成立，得到 $\Delta_0=P_1+zyP_0=1-z$。我们先求出 $P_i$ 的特征方程： $$ x^2-(1-z(1+y))x+z^2y=0. $$ 设两个特征根为 $x_1,x_2$，则 $$ x_1+x_2=1-z(1+y), \qquad x_1x_2=z^2y. $$ 如果直接套求根公式，就会出现根号。我们不妨再设个中间变元 $u$。根据 $x_1x_2=z^2y$，令 $$ x_1=\frac zu,\qquad x_2=zyu. $$ 这样乘积已经满足要求，再代入根的和： $$ 1=x_1+x_2+z(1+y) =z\left(\frac1u+yu+1+y\right). $$ 因此 $$ \boxed{z=\frac{u}{(1+u)(1+yu)}.} $$ 为了少写一点，记 $$ \Phi(u)=(1+u)(1+yu). $$ 那么 $$ z=\frac{u}{\Phi(u)}, \qquad x_1=\frac1{\Phi(u)}, \qquad x_2=\frac{yu^2}{\Phi(u)}. $$ 这里选择满足 $u(0,y)=0$ 的分支，也就是把 $u$ 看成方程 $u=z\Phi(u)$ 确定的形式幂级数。注意到我们可以用 $x_1,x_2$ 重写 $P_i$： $$ P_i=\frac{x_1^{i+1}-x_2^{i+1}}{x_1-x_2}. $$ 代入后， $$ P_i\left(\frac{u}{\Phi(u)},y\right) = \frac{1-(yu^2)^{i+1}} {(1-yu^2)\Phi(u)^i}. $$ 把换元后的行列式记为 $$ \widehat\Delta_h(u,y) := \Delta_h\left(\frac{u}{\Phi(u)},y\right). $$ 由 $\Delta_h=P_{h+1}+zyP_h$，得到 $$ \begin{aligned} \widehat\Delta_h &= \frac{1-(yu^2)^{h+2}+yu\bigl(1-(yu^2)^{h+1}\bigr)} {(1-yu^2)\Phi(u)^{h+1}}\\ &= \frac{1+yu-y^{h+2}u^{2h+3}(1+u)} {(1-yu^2)\Phi(u)^{h+1}}. \end{aligned} $$ 再把分子里的 $1+yu$ 提出来。设 $$ X_h(u,y) = y^{h+2}\frac{u^{2h+3}(1+u)}{1+yu}, $$ 那么行列式就变成 $$ \boxed{ \widehat\Delta_h(u,y) = \frac{1+yu}{1-yu^2} \cdot \Phi(u)^{-(h+1)} \cdot \bigl(1-X_h(u,y)\bigr). } $$ 先记住这个形式：第一项与 $h$ 无关，第二项只在指数上与 $h$ 有关，最后一项里的 $X_h$ 至少带着 $y^{h+2}$。这三点后面都会用到。 ##### 9.5 拉格朗日反演行列式已经写出来了，不过我们要求的是 $z^n$ 的系数，现在的式子却是用 $u$ 表示的。没关系，我们用拉格朗日反演转回来。由于 $u=z\Phi(u)$，对于形式幂级数 $G(u,y)$，拉格朗日反演给出 $$ \boxed{ [z^n]G(u(z,y),y) = \frac1n[u^{n-1}] \frac{\partial G(u,y)}{\partial u} \Phi(u)^n. } $$ 求导时把 $y$ 当作固定参数即可。令 $G(u,y)=\log\widehat\Delta_h(u,y)$。因为 $$ \Delta_h(z,y) =\widehat\Delta_h(u(z,y),y), $$ 所以 $$ \boxed{ F_h(y) = -[u^{n-1}] \left( \frac{\partial}{\partial u} \log\widehat\Delta_h(u,y) \right) \Phi(u)^n. } $$ 这也就是原先的留数写法： $$ F_h(y) = -[u^{-1}] \left( \frac{\partial}{\partial u} \log\widehat\Delta_h(u,y) \right) \left(\frac{\Phi(u)}u\right)^n. $$ 两种写法完全相同。下面用 $[u^{n-1}]$ 的形式，这样提取系数时只需要看非负次幂。 ##### 9.6 先计算修正量，能消掉的就不算了现在来计算 $m\le k$ 时的修正量。根据上一节， $$ [y^m](F_m-F_k) = -[u^{n-1}y^m] \left( \frac{\partial}{\partial u} \log\frac{\widehat\Delta_m}{\widehat\Delta_k} \right) \Phi(u)^n. $$ 我们分别计算两个迹时，看上去要处理很多项。不过先把行列式相除，就发现第一项直接消掉了： $$ \frac{\widehat\Delta_m}{\widehat\Delta_k} = \Phi(u)^{k-m} \frac{1-X_m(u,y)}{1-X_k(u,y)}. $$ 因此 $$ \log\frac{\widehat\Delta_m}{\widehat\Delta_k} = (k-m)\log\Phi(u) + \log(1-X_m) - \log(1-X_k). $$ 后面两项还要算吗？注意到我们现在只取 $y^m$ 的系数： - $X_m$ 至少含有 $y^{m+2}$，因此 $\log(1-X_m)$ 中的每一项也至少含有 $y^{m+2}$。 - $X_k$ 至少含有 $y^{k+2}$，而 $k\ge m$，所以 $\log(1-X_k)$ 同样不会含有 $y^m$ 或更低次的项。这里用到的是 $$ \log(1-X)=-\sum_{r\ge1}\frac{X^r}{r}. $$ 再检查一下后续操作：对 $u$ 求导不会改变 $y$ 的次数，而 $\Phi(u)^n=(1+u)^n(1+yu)^n$ 只含有 $y$ 的非负次幂。因而这两项在整个系数提取过程中，都不可能贡献 $y^m$。所以最后只剩 $$ \begin{aligned} [y^m](F_m-F_k) &= (m-k)[u^{n-1}y^m] \frac{\Phi'(u)}{\Phi(u)}\Phi(u)^n\\ &= (m-k)[u^{n-1}y^m] \Phi'(u)\Phi(u)^{n-1}. \end{aligned} $$ 我们手动求一下导： $$ \frac{\Phi'(u)}{\Phi(u)} = \frac1{1+u}+\frac{y}{1+yu}. $$ 于是需要提取系数的部分是 $$ \Phi'(u)\Phi(u)^{n-1} = (1+u)^{n-1}(1+yu)^n + y(1+u)^n(1+yu)^{n-1}. $$ 对于第一项，先从 $(1+yu)^n$ 中取 $y^m u^m$，再从 $(1+u)^{n-1}$ 中取 $u^{n-1-m}$，得到 $$ \binom nm\binom{n-1}{n-1-m} = \binom nm\binom{n-1}{m}. $$ 对于第二项，外面已经有一个 $y$，所以从 $(1+yu)^{n-1}$ 中取 $y^{m-1}u^{m-1}$，再从 $(1+u)^n$ 中取 $u^{n-m}$，得到 $$ \binom{n-1}{m-1}\binom n{n-m} = \binom nm\binom{n-1}{m-1}. $$ 把两项加起来，恰好是 $$ \binom nm \left(\binom{n-1}{m}+\binom{n-1}{m-1}\right) = \binom nm^2. $$ 因此 $$ \boxed{ [y^m](F_m-F_k)=(m-k)\binom nm^2 \qquad(0\le m\le k). } $$ 这个形式就漂亮很多了。先相减之后，我们只用了一次简单的二项式展开，就得到了全部修正量。 ##### 9.7 计算宽松总数 $F_k(1)

修正量已经处理完了，现在只需要计算宽松总数 F_k(1)。这里没有固定区间数的要求，直接令 y=1，就是把所有 m 的系数加起来。

令 L=2k+3。代入 y=1 后，

\Phi(u)=(1+u)^2, \qquad X_k(u,1)=u^{2k+3}=u^L.

于是行列式又能化简：

\begin{aligned} \widehat\Delta_k(u,1) &= \frac{1+u}{1-u^2} (1+u)^{-2k-2}(1-u^L)\\ &= \boxed{ \frac{1-u^L}{(1-u)(1+u)^{L-1}}. } \end{aligned}

对于分母，都是乘积的形式，放进 \log 里就拆开了：

\log\widehat\Delta_k(u,1) = \log(1-u^L) - \log(1-u) - (L-1)\log(1+u).

手动求一下导，再用拉格朗日反演，有

F_k(1) = [u^{n-1}](1+u)^{2n} \left( \frac{Lu^{L-1}}{1-u^L} - \frac1{1-u} + \frac{L-1}{1+u} \right).

对于上面的三项，我们分别提取系数。

对于项 1：

先用等比数列展开：

\frac{Lu^{L-1}}{1-u^L} = L\sum_{j\ge1}u^{jL-1}.

因此

[u^{n-1}](1+u)^{2n} \frac{Lu^{L-1}}{1-u^L} = L\sum_{j\ge1}\binom{2n}{n-jL}.

这里实际上只有 jL\le n 的项非零。

对于项 2：

由于 1/(1-u)=\sum_{r\ge0}u^r，

-[u^{n-1}]\frac{(1+u)^{2n}}{1-u} = -\sum_{r=0}^{n-1}\binom{2n}{r}.

利用二项式系数关于中间项对称，

2\sum_{r=0}^{n-1}\binom{2n}{r} + \binom{2n}{n} =2^{2n}.

所以这一项为

-2^{2n-1}+\frac12\binom{2n}{n}.

对于项 3：

这一项可以直接提取：

[u^{n-1}](1+u)^{2n} \frac{L-1}{1+u} = (L-1)\binom{2n-1}{n-1} = \frac{L-1}{2}\binom{2n}{n}.

把三项加起来，得到

F_k(1) = L\sum_{j\ge1}\binom{2n}{n-jL} + \frac L2\binom{2n}{n} - 2^{2n-1}.

最后再利用 \binom{2n}{n-jL}=\binom{2n}{n+jL}, 就可以统一写成

\boxed{ F_k(1) = \frac L2\sum_{j\in\mathbb Z}\binom{2n}{n+jL} - 2^{2n-1}. }

9.8 答案与计算

回到最开始的计数式：

\operatorname{Ans}_{\mathrm p}(k) = F_k(1) + \sum_{m=0}^{k}[y^m](F_m-F_k).

将两部分代入，就得到最终答案：

\boxed{ \begin{aligned} \operatorname{Ans}_{\mathrm p}(k) ={}& \sum_{m=0}^{k}(m-k)\binom nm^2\\ &+ \frac{2k+3}{2} \sum_{j\in\mathbb Z} \binom{2n}{n+j(2k+3)} - 2^{2n-1}. \end{aligned} }

10. 小结

太长不看版，结尾自取模板。

情形	答案
链·边覆盖	\sum_j\bigl[\binom{2n}{n-2j(k+2)}-\binom{2n}{n+2-2j(k+2)}\bigr]
链·点覆盖	\sum_j\bigl[\binom{2n}{n+j(2k+3)}-\binom{2n}{n+2+j(2k+3)}\bigr]
环·边覆盖	\sum_{m\le 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}
环·点覆盖	\sum_{m\le k}(m-k)\binom{n}{m}^2 + \frac{2k+3}{2}\sum_j\binom{2n}{n+j(2k+3)} - 2^{2n-1}

写在最后

事实上，这题是[2026“钉耙编程”中国大学生算法设计春季联赛（7）1003 Live house](1003 Livehouse) 的加强版。

虽然写了这么多，但做题的时候只需要推一小部分，剩下的也能靠猜式子猜出来，这么一想这题还是简单了qaq。主播比较菜了，用了 AI 还要推近半个月qaq。

人生第一次出题，希望各位能从这道题中学到一点东西qaq