循环引理和变态双射题

· · 题解

这个问题实际上存在一个非常巧妙的双射做法（官方题解），这个做法的思维难度极高，但过程很短，核心代码只有一个两重循环的 DP。

非常可惜的是，现有的中文题解几乎都改编自 jiangly 老师的做法，这个做法仍然优美，但推导过程和实现略复杂。

这个题解详细揭秘了官方题解的精彩双射，希望能帮助大家学习。

在下文中，记一个序列的任意一个不为空的前缀是 非空前缀，记一个长为 n 序列的任意一个长度 \lt n 的前缀是 真前缀。

前置知识：循环引理

给定整数序列 a_1, a_2, \dots, a_n 满足：

则在该序列的 n 个循环移位中，恰有 S 个移位满足其 非空前缀和 \gt 0。

对于这个性质的证明，可以考虑其最后一次前缀和达到 1, 2, \dots, S 的 S 个位置，可以证明从它们是符合要求的，这里不再展开。

在下文中，我们需要用到循环引理的一个 等价形式。

等价形式：给定整数序列 a_1, a_2, \dots, a_n 满足：

则在其所有循环移位中，恰有 S 个满足：它可以被 唯一 划分为 S 个 基本块。其中，每个基本块满足两个性质：

证明：把 a 所有元素取相反数，两个限制与循环引理的两个限制相同。

那么，这个序列恰有 S 个循环移位满足其任意 后缀和 \gt 0。

这意味着它的每个 真前缀和 都 \lt S，在这个条件下，我们只需按它第一次到达 1, 2, \dots, S 这些位置来划分即可，其中第一次到达 S 时，前缀长度为 n（即整个前缀）。

再把所有元素取相反数回来，可以得到原结论。

解法

首先，题目中认为数值相同的卡片相同，我们可以通过简单的组合技巧，转化为所有卡片均不同的计数。下文中，我们主要解决的就是这种情况的计数。

题目中，每一次获得硬币都对应一次从 0 出发，最终回到 0 的过程。

每一个过程涉及至少 1 张正数卡片。我们断言，可以为每一枚硬币（每个过程）唯一关联一张正数卡片，称为 主导卡片。

记我们选的主导卡片是 l_1, l_2, \dots, l_k，并记 T = \sum l_i。

记剩下的卡片集合为 R，显然 R 的总和是 -T。

我们定义一个 基本块 是满足下面两个性质的序列：

根据 前置知识，任何一个总和为 -T，且各个元素 \ge -1 的整数序列，它的所有循环移位中 恰有 T 个，使得它能 唯一 分解为 T 个子段，满足每个子段都是基本块。

考虑求出这样的划分，我们看看现在有什么：总和为 T 的主导卡片，以及 T 个基本块。

我们把这些子段再按照主导卡片的值分组，然后把主导卡片插入这些子段中。

这样，一张值为 x 的主导卡片会分配到 x 个子段，这对应了 x + 1 种插入方式。

我们把上面提到的方案统合起来：先枚举 k 个主导卡片集合 R，记 S 是总卡片数（与题面一致），T = \sum_{x \in R} a_x，那么 k 个 0 的序列数就是：

\sum_{R \subset U, |R| = k} \left( \frac{T}{S - k}\prod_{i \in R}(a_i + 1) \right)

有几个细节问题：

证明

上面这个方式本质是一个神秘的双射，它构造了一个从原序列到我们的基本块结构的一一映射。只要证明了这个双射的正确性，我们不难验证整个算法的正确性。

结构到序列的映射

根据基本块的性质 1, 2，可以推出性质 3：对于任意 t 基本块拼接在一起的序列，每个真前缀和都应该 \gt -t。

性质 3 同样意味着性质 4：每个非空后缀和 \gt 0。

考虑 t 个基本块，并把一个值为 t 的主导卡片插入其中，我们需要使得插入之后，除了空前缀与全局和，没有一个前缀和 = 0。事实上，假设我们插入 t 并使得序列划分为 [L, t, R] 之后，我们只需把 L 这一部分反转即可。注意，这里的反转是从 卡片 层面反转，而非更大块的 基本块 层面。

证明：如果前缀是在 t 之前截取的，根据性质 4 这个前缀肯定 \gt 0，不满足要求；否则，未截取的后缀肯定 \gt 0，那么截取的前缀肯定 \lt 0，同样不满足要求。

这是一个部分的映射，对于多个部分，只需要分别映射即可。

这样，我们证明了 结构到序列的映射。

序列到结构的映射

首先，通过 k 个 0 的位置，我们把序列划分为 k 部分。

对于每一个部分，我们希望证明它唯一对应上面的那个结构 [L, t, R]，其中 t 是主导卡片。换句话说，t 唯一。

类似上文证明的过程，我们不难发现：在 L 这一部分，前缀和从 0 逐渐下降到一个 -x(0 \le x \le t)，然后直接提升到 -x + t，然后在 R 的这部分逐步下降到 0，所以，这部分除了开头和结尾，不会出现一个多余的 0。

因此，我们也构造出了 序列到结构的映射。

实现

我们主要计算这个式子：

\sum_{R \subset U, |R| = k} \left( \frac{T}{S - k}\prod_{i \in R}(a_i + 1) \right)

把 S - k 提到外面，一个主要问题是计算 T。

我们把 T 组合意义拆开，拆成 \sum_{i \in R} a_i。我们逐个加入 R，并枚举一个元素为特殊元素，其权值乘上 a_i，那么恰有一个特殊元素的序列权值积，就是处理 T 之后上面这个乘积式的值。

记 dp_{i, 0/1, j} 表示考虑前 i 个元素，选中 j 个，其中 0/1 个特殊元素，我们计算的积和式的值。转移容易做到 O(n^2)，同时还可以去掉第一维 i 并原地转移。

事实上还能进一步使用多项式优化，这里不展开。

提交记录