集合划分容斥，后面忘了

· · 算法·理论

upd 3.20：更新了两个集合划分容斥的题放在最后，更新了简单的双线反射容斥。

是时候学习说话了。

集合划分容斥

可能没有明确的定义。

有一种经典的模型就是：

给你一个长度为 n 的满足某种条件的颜色序列 c_i。

如果我们给每个长度为 c 的极长颜色段赋 [x^c]F(x) 的权值。一个颜色序列的权值是所有极长颜色段权值的乘积。那么求所有颜色段权值乘积的和。

那么我们对整个序列做一组区间划分，这样划分出的每一个区间颜色都相同，那么划分出长度为 c 的区间权值为 [x^c]G(x)。

根据定义，每个长度为 c 的极长颜色段独立。

不妨定义 G 的常数项是 0。用 G 组合出这个颜色段的 GF，可以得到 F=\dfrac{1}{1-G}。

然后根据这个公式就可以解出 G=1-\dfrac{1}{F}。集合划分容斥大概就是这么一回事。

所以看起来是容斥，其实更像反演？

字符串的迹象

原题链接。

做法

可能是模板题。

显然我们可以设 F(x)=1+x+x^2+x^3+x^4+...+x^{k-1}=\dfrac{x^k-1}{x-1}。

然后算出 G(x)=\dfrac{x^k-x}{x^k-1}。

若统计的连续段长度为 n，则：

对于每种字符，先确定其分成 j 段的答案，然后再把所有字符的答案合并，也就是多重集的组合数。

然后这个显然可以 dp。于是就算完了。

时间复杂度 O((\sum a_i)^2)。

总结

这个题好像也差不多。

Yet Another ABC String

原题链接。

做法

可能也是模板题。显然要刻画的条件是上升段长度 \le 2。

根据上一题的结论，我们需要按照对 3 的余数给每一段赋权。

然后用三元生成函数刻画一个段：

G(a,b,c)=(a+b+c)\sum_{i=0}^{\infty} (abc)^i-3\sum_{i=1}^{\infty}(abc)^i\\ =(a+b+c-3abc)\sum_{i=0}^{\infty} (abc)^i\\ =\dfrac{a+b+c-3abc}{1-abc}

然后如此计算：

H=\dfrac{1}{1-G}\\ =\dfrac{1}{\frac{1+2abc-a-b-c}{1-abc}}\\ =\dfrac{1-abc}{1+2abc-a-b-c}\\ =(1-abc)\sum_{i=0}^{\infty} (a+b+c-2abc)^i

对于第一项，直接枚举并且算两遍。

对于第二项，考虑看 (a+b+c)^i 选了几项即可。

复杂度 O(n)。

某个题

长度为 n 的排列，不存在一个长度为 k 的区间，使得这个区间内相邻的两个数的差都为 1，求这样的排列的数量。

原文。

先解决极长的限制。

解决方法是类似的，显然 F(x)=\dfrac{x-x^k}{1-x^k}。

然后再进一步确定系数。显然 [x^n]H(x)=[x^n](1+[n\ge 2])F(x)。

可以得到 H(x)=\dfrac{x-2x^k+x^{k+1}}{1-x^k}。

然后我们要算的是：

\sum_{i=0}^{\infty}i!H^i

后面先不推，等我先学一下怎么系统解递推式。

大概就是，D-finite？因为这是一个函数复合。反正我是不会这些东西的。而且还需要机械求整式递推。

上面这个东西如果暴力做可以 O(n^2)。

DAG 容斥

题意：给你一个 n 个点的无向图，问给其定向得到 DAG 的方案数。

设 dp_S 是 S 的导出子图为 DAG 的方案数。

计算 S 时，钦定一个点集 T\subseteq S，令这个点集是入度为 0 的。

那么我们有结论：

dp_S=\sum_{T\subseteq S,T\neq \varnothing} 2^{coef(T,S/T)} dp_{S/T} (-1)^{|T|+1}

考虑怎么证明。

先假设所有 S 的真子集 S' 的 dp_{S'} 都能算对。

考虑先行枚举一种可行的 DAG。记这个 DAG 实际上入度为 0 的点集为 T_0。

由于 dp_{S/T} 都算对了，对这种可行的 DAG 的贡献是 1，那么会产生贡献的 T\subseteq T_0,T\neq \varnothing。

可以说明，所有会产生贡献的 T 的容斥系数之和为 [T_0\neq \empty]。

总结：DAG 容斥其实是集合划分容斥的思路，也就是对于每种确定的方案都要算对贡献。

容斥

新的定义

我们尝试更加形式化的定义容斥。

现在有两个集合 U,S，S 是最终要得到的计数对象，我们最终所求即为 |S|。S 是 U 的一个子集。

|S| =\sum_{a\in U}h(a)

其中 h(a) 就是 [a\in S]。容斥实际上仅仅是对上面这个问题做了变换。记 g(x,y) 是定义在 (U,U)\to \mathbb{R} 上的函数。

\sum_{a\in U}h(a)=\sum_{a\in U}\sum_{b\in U}g(a,b)=\sum_{b\in U}\sum_{a\in U}g(a,b)=\sum_{b\in U}f(b)

可以看到以下两个等式：

h(a)=\sum_{b\in U}g(a,b)\\ f(b)=\sum_{a\in U}g(a,b)

关键其实在于构造 g 使得 f 更好算。

构造方法

一种常见的构造方法，参见我会容斥，通过把条件逻辑拓展实数范围内，再做四则运算，把 h(a) 直接给拆开来了，因为不需要观察 f(b)，是一种较好的方法。

对上面做一个简要的介绍，比如我们解决了二项式反演类问题，就把 \prod x^{a_i}（a_i 是 01 变量）拆成 \prod a_i(x-1)+1 就好了。

在实际运用中，这应该是二项式反演的严格上位替代。

一般意义上的集合划分容斥，先找一个好统计的集合 P，f(b)=[b\in P]f_0(b)，然后再尝试从 a 的系数推到 f_0(b)。

那比如说上面说的第一种集合划分容斥，我们好统计的集合就是不需要满足连续段极长限制的一组划分 b。

对于最后要统计上的颜色序列 a 及其真正极长连续段划分，都可以被一些 b “捕获”，这对应了 g(a,b)=c(a,b)l(b)，其中 c(a,b) 表示 a 是否可以被 b 捕获。构造的 l(b) 要让 [a\in S]=\sum_{c(a,b)} l(b)。

那么 f(b)=l(b)(\sum_{c(a,b)} 1)，这契合我们的结论。其实 a 和 b 所在的集合还可以不一样来着，懒得管了（

如果用矩阵表达，那就是 A(GB)=(AG)B，其中 A,B 分别是一个行向量和一个列向量。

反演

然后就是所谓的反演。我们设计两个矩阵 A,B。令 C=AB，那么有 C_{i,j}=\sum_{k=1}^n A_{i,k}B_{k,j}。假设 C 是单位矩阵。

那么 f=Bg 就可以得到 g=Af。所以反演就是一种求逆方法。

假设 B 是下三角矩阵，如果要求任意情况下的容斥系数就可以解方程做到 O(n^2)。

第一，如果对 a,b 分别做了一次正变换，点积起来，然后做逆变换（反演）就可以得到一种卷积，FFT 和 FWT 都是这个思路。

第二，如果这个矩阵有更好的写法，那么可以改写。

举个例子，比如莫比乌斯反演。倍数关系可以写成生成函数 \prod_{i=1}^{\infty} \frac{1}{1-x_i}，其中 x_i^j 表示第 i 个质因子有 j 个。那么逆变换显然就是 \prod_{i=1}^{\infty} (1-x_i)，这和莫比乌斯函数是一样的。当然这其实就是 DGF。

前缀和与差分

原题链接。

做法

\sum_{a}\gcd(a_1,a_2,a_3,...,a_n)^2\\ \sum_{a}\sum_{d|a_i} h(d)\\ \sum_{d=1}\lfloor{\frac{m}{d}}\rfloor^nh(d)\\ \sum_{d=1}\left(\sum_{k\le\frac{m}{d}}k^n-(k-1)^n\right)h(d)\\ \sum_{i=1}^m\sum_{dk=i}f(k)h(d)

先考虑 h 是啥。还是根据上面的 DGF 得到 h 的狄利克雷生成函数就是 \dfrac{\zeta(x-2)}{\zeta(x)}。这个反正可以线性筛。

然后就是积性函数卷非积性，然后再前缀和一下。就是积性函数卷非积性函数怎么做的问题。

我们尝试着压缩一下信息。把 h 拆成若干个只包含单一质数的积性函数 h_2,h_3,h_5,h_7,\dots。这些函数只在他们对应的 h_p(p^k) 上有值。

然后依次卷上每一个质数就好了。i 会贡献到 ip,ip^2,ip^3,\dots 这些数，那么只需要倒序转移就行了。

总结

这个题，虽然不是一个传统意义上的容斥题，但是却深刻蕴含了容斥的思想。比如它待定了 h 的系数，比如它通过前缀和与差分拆解了一个难算的和式。

不等关系

题意：给你一个 01 序列 s。请计数满足 [p_i<p_{i+1}]=s_i 的排列 p 的个数。

做法

还是使用容斥，我们做如下的拆贡献：如果 s_i=1，那么贡献为 [p_i<p_{i+1}]，否则为 1-[p_i<p_{i+1}]。

先找出所有上升段的长度 l，然后在上升段之间钦定是否容斥。

考虑 dp 算这个东西。设当前考虑到前 i 个上升段。

枚举一个段 j，j+1\sim i 之间的段全部容斥成一个段。

f_i=\sum_{j=0}^{i-1} \dfrac{f_j (-1)^{i-j+1}}{(ls_i-ls_j)!}

这个半在线卷积就好了，CDQ 可以 O(n\log^2 n)。

总结

这个题好像没什么特殊的点，可能只是在这混个片场。

欧拉？欧拉！

原题链接。

逐步容斥

先讲出逐步容斥的理论基础。我们的条件形如：\displaystyle \prod_{i=1}^n [p_i=0]x+[p_i=1]y。那么有三种拆法：

那么什么是逐步容斥？我们先拆出来前 j-1 项，于是乘积式分成 \displaystyle C\prod_{i=j}^n [p_i=0]x+[p_i=1]y。

那这个时候我们根据前面 j-1 个位置的决策，自然可以决定新位置是三种拆法的哪一种。

做法

原题所求即 \displaystyle \prod_{i=1}^{n}x^{[p_i>p_{i+1}]}y^{[p_i>i]}。

先把 y^{[p_i>i]} 拆成 [p_i\le i](1-y)+y。

但是 x^{[p_i>p_{i+1}]} 不应该急着拆，先考虑怎样拆好算。

现在考虑如下问题：我们把排列分成了若干段，第段长度为 L_i+R_i+1。这段有一个特殊的位置叫做 c。然后我们令这个段合法的条件为：

\prod_{j=c-L_i}^{c-1}[p_j<p_{j+1}]\prod_{j=c+1}^{c+R_i}[p_j<p_{j-1}]

也就是一个单峰段。另外要求 p_c\le a_i。粗略的讲，这个段形如 <<<>>>>。

为了解决这个问题，我们按照 a_i 从小到大排序填数。

第 i 次考虑了所有 1\sim a_i 的数（注意不是位置），记之前 i-1 次已经填了 s 个，那么这次可以填 a_i-s 个。那么这次的方案数为：

\binom{a_i-s}{L_i+R_i+1}\binom{L_i+R_i}{L_i}

显然是独立的，乘起来就好了。

回到原问题。如果我们采用一种叫做逐步容斥的思路，能否利用到上一个问题呢？

不妨假设前 i-1 个数已经容斥好了。这意味着，前 i-1 个数形成了若干个段，每段的限制都是单峰。

仔细思考上面的拆法。对于一个段第一次出现 p_i\le i 这个限制之前，都只允许 < 的限制，而在一个段之后出现这个限制时，我们又可以无视 p_i\le i 了。而当我们选择无限制时，这个段就被终结了。

然后口胡一下 O(\mathrm{poly}(n)) 的 dp 怎么写吧。状态要记 f_{i,j,k,l} 表示前 i 个数枚举了 j 个段，k 个 p_i\le i 的限制，当前这些段中有限制的长度的和为 l。

然后就是转移，如果从 j 转移到 i，意味着一段长为 i-j 的段被新生成了。判掉这段中一个限制都没有的情况。

如果其中第一个 p_i\le i 的位置就是 c，那么对 x 的贡献就是：(x-1)^{i-j}(-x)^{c-j}。对 y 的贡献就是 (1-y)y^{c-j-1}。这样在算算系数大概就能做 O(n^6) 了。但是我不会 O(n^5) 所以还没写，懒了。

比赛

原题链接。

做法

考虑如何计算一种排列的权值。可以发现答案形如 [R>B]-[B>R]-[R<B]。但是我们又有一个等式：[R<B]+[R>B]=[B>R]+[B<R]。可以得到 [B<R]-2[R<B]。

考虑指定若干对异色的 (a,b)，表示 a 的后继是 b 并且 a<b。

对于一个红队的人，指定一个比他大的的蓝队，和蓝队指定一个比他大的红队，这两件事情是独立的。所以可以分成两次 dp。最后可以得到指定了 x 对 [B<R]，y 对 [R<B] 的方案数。剩下的就是随意组出一个环。然后做二维二项式反演就好了。

时间复杂度 O(n^2\log n)。

The Best Problem of 2021

原题链接。

问题泛化

定义最简基是一个线性基，满足其主元列只有恰好一个 1。容易发现一个线性空间对应唯一一个最简基。

对 B 高斯消元，得到一个最简基。最简基有另一个性质是：

首先满足 B_1>B_2>B_3>\dots>B_n。定义 \mathrm{hi}(x) 为 x 的最高位，那么 \mathrm{hi}(B_1)>\mathrm{hi}(B_2)>\mathrm{hi}(B_3)>\dots>\mathrm{hi}(B_n)。每个数的最高位就是主元位。

那么我们设计一个二进制数 f(x)，如果这个数第 i 位是 1，那么 x 就要异或上 B_{n-i}。这样 x 在这个线性空间中的排名就是 C+1。

那么对于原题里的 X，我们可以二分找到一个对应的 X'，满足所有 f(x)\le X' 的数，x\le X。

容斥或反演

问题现在变成了 [1,X] 中有多少个满秩的集合。也就是秩为 n。

可以算的是一个秩为 i 的最简基去张成集合 S，然后在 S\cap[1,X] 中任选一个子集。设这个答案为 g_i。

现在一个集合的实际秩为 c，那么其会被 g_c,g_{c+1},g_{c+2},\dots,g_{n} 算到。

记实际秩为 i 的集合被 g_j 算到的次数为 C(i,j)。

现在我们设一个容斥系数 \mathcal{H}_i，最后答案是 g_i\mathcal{H_i} 的和。

那么我们可以得到 \mathcal{H}_n=1。接下来考虑算 \mathcal{H}_{n-1}，那么就要减去 C(n-1,n)\mathcal{H}_n。

以此类推可以得到暴力反演式：

\mathcal{H}_j=-\sum_{k=j+1}^n C(j,k)\mathcal{H}_k

验证一下，此时一个实际秩为 c 的集合会被贡献 C(c,c)\mathcal{H}_c+C(c,c+1)\mathcal{H}_{c+1}+\dots+C(c,n)\mathcal{H}_n。根据定义这样会被算恰好 0 次。

当然上面都是废话，接下来补充一下细节。

细节

比如 C(i,j) 到底是什么？我们给秩为 i 的集合 S 消元，那么其可以对应一个秩为 j 的最简基吗？如果我们记 f(i,j) 为 [0,2^{i}) 中秩为 j 的最简基数量，那么 C(i,j)=f(n-i,j-i)。证明可以考虑往剩下的位里面塞一个最简基，然后如果冲突了就消元，这样可以构成单射，另外一个方向的单射也是类似的。

考虑怎么算 f(i,j)。有递推式 f(i,j)=f(i-1,j)+f(i-1,j-1)2^{i-j}。这其实是 q-二项式系数，但是我不懂，就不管了。边界条件是 f(i,0)=1。

然后是 g_i 怎么求？

如果 X 够大，那就没有这个烦恼，直接套用 f(n,i)2^{2^i} 就好了。这提示我们 dp。

先想想怎么求这个基中 X 的 \mathrm{rank}。答案就是 2^{\mathrm{rank}(X)}。

考虑贪心，从高往低看最简基，有四种情况：

听起来有点绕，其实就是从高到低比较每一位。

那么我们的答案是怎么计算的呢？显然到第一，三种情况就可以停了。又比如我们选了最高的数，那么其四种情况：

第三，四种情况，直接找一个比 X 小或大的最高数，然后后面就是算类似 f 的东西。

第一种情况，不选最高数的贡献可以直接乘上了，然后就是继续 dp。后面最高数因为一直被选，可以起到一个干扰的作用，说的很迷惑，其实就还是乘上最高数乱选的贡献。

第二种情况，最高数可以直接扔掉了，也是乱选，然后就是继续 dp。总之每次 dp 到一处时，前面的主元就是可以凑出 X 的。

另一些细节

但是上面这个 dp 过程要从高往低 dp，还要记之后选了几个之前选了几个，有点爆，我们再整理一下。

比如我们不妨钦定最高位 n 一定被选，显然如果 X 不选这一位那么总体的答案就直接是 0 了。这样做的目的是保护每一个非主元位，出现 0 和出现 1 的概率是一致的。

那么我们做一个转化，我们可以去钦定非主元位是一个数 0/1，这样和实际方案冲突的概率只有 \dfrac{1}{2}，合起来就是 \dfrac{1}{2^{n-i}}，最后乘上就行。

我们从低往高 dp，求 g(i,j) 表示低 i 位选了 j 个基，最后在低 i 位可以 \le X 的方案数。

这个定义有些抽象，但是应该可以理解。毕竟前面那些位已经 =X 了。

考虑 g(i,j) 转移 X 这一位是 0：

考虑 g(i,j) 转移 X 这一位是 1：

总结

我现在实力不是很配评价这个题，就不评价了。

注意消元时要先写线性基然后再从低往高调整。虽然我也还不知道为什么。

[ABC236Ex] Distinct Multiples

原题链接。

做法

钦定一个集合划分，使得每个集合内部的数相等。

假设我们钦定大小为 i 的集合容斥系数为 \mathcal{H}_i，则有一个指数生成函数 H(x) 描述容斥系数。

我们要求 \exp H(x)=x+1。那么我们有 H(x)=\ln(x+1)。可以得到 \mathcal{H}_i=(-1)^{i+1}(i-1)!。实在不行就打表。

剩下就是对于一个集合，其方案数是 m 除以集合内所有 D_i 的 \mathrm{lcm}。然后只需要用集合幂级数 \exp 就可以了。

时间复杂度 O((n^2+\log V)2^n)。

双线反射容斥

先不写代数化。单线反射容斥代数化可以看 EI 的博客。

引入

一个人在 [0,n] 上游走，不可以出去，走 t 秒从 a 走到了 b。求方案数。

做法

转化一下，比如一个平面直角坐标系，不能碰到 y=x+a 和 y=x-b，从 (0,0) 开始，每一步可以向上向右走，问你到达 (X,Y) 的方案数。

假设只有一条直线 y=x+a，怎么做？

考虑双射，把 (0,0) 到点 (X',Y') 的一条路径与一条不合法路径建立双射。其中 (X',Y') 是 (X,Y) 对 y=x+a 的对称点。

只需要记录第一次碰到 y=x+a 时的点 K，把点 K 及之后的路径翻折一下就好了。

现在有两条直线，怎么做？

有一个单纯的想法是只减去分别经过这两条直线的方案。

然而这显然会算重。只需要考虑分别经过这两条直线就好了。

那现在怎么做？比如我们先经过了 y=x+a，然后经过 y=x-b。那么第一次碰到 y=x+a 是在 A 点，第二次是在 B 点。这和什么产生双射？

先展开最后的翻折。把 B 到 (X,Y) 的路径翻折后，得到 (X',Y')，又可以得到 (X'',Y'')。

具体的细节是，一个点 (X,Y) 沿着 y=x+c 对称后，会得到 (X',Y')。那么这两个点的线段是关于 y=x+c 垂直的，所以有 X+Y=X'+Y'。又根据距离公式，有 Y-X+Y'-X'=2c。

解方程，可以得到 (X',Y')=(Y-c,X+c)。

更进一步

接下来考虑更加形式化的容斥。我们有两种操作：

  1. 沿 y=x+a 翻折，得到 Y-a,X+a。
  2. 沿 y=x-b 翻折，得到 Y+b,X-b。

对于一种路径，其可以被简化成反复的经过直线 y=x+a 以及 y=x-b。根据之前的推理，如果重复经过，那么就没有意义。

接下来假设路径的“标识符”是 \mathtt{ABABABABA}。每次我们都只能匹配一个长度的子序列 \mathtt{ABA} 或 \mathtt{BABA} 之类，并加上他们的容斥系数 \mathcal{H}，最后我们要让标识符非空的路径贡献为 0，空的路径贡献为 1。

然后推导容斥系数。首先 \mathcal{H}(\varnothing)=1，\mathcal{H}(\mathtt{A})=\mathcal{H}(\mathtt{B})=-1。

然后可以得到 \mathcal{H}(\mathtt{AB})=\mathcal{H}(\mathtt{BA})=1。

然后可以得到 \mathcal{H}(\mathtt{ABA})=\mathcal{H}(\mathtt{BAB})=-1。

注意这里的匹配最多一次，也就是子序列 \mathtt{A} 只被 \mathtt{ABA} 捕捉一次。

可以得到长度为 i 的字符串容斥系数为 (-1)^i。

由于两条直线的切换最快需要 a+b 步，所以时间复杂度为 O(\dfrac{X+Y}{a+b})。

总结

其实只是初探，没怎么细究。

细究的话要单开一篇。

全文总结

然后就先写到这里，如果后面出现了啥好写的再写写。