容斥原理

标签：gcd limits sum 容斥 times 原理 sta

概述

容斥原理是正难则反思想的实践产物。（23.1.15 upd：存疑）
即，在正向求解问题过于困难时，考虑逆向求出不合法方案数，然后用总方案数减去以得到合法方案数。
大体上，可以分为以下两类：

子集容斥

一般的容斥原理指的就是子集容斥。其是如下的一种容斥：
不妨称“合法”为满足 \(k\) 个条件，并抽象为条件的集合，则有如下的一般形式：

\[ans=\sum\limits_{S=\varnothing}^{full} (-1)^{|S|}\times res_{S} \]

这里 \(res_S\) 为满足的条件包含 \(S\) 的方案数。
用自然语言描述，就是所有情况（所有条件都爱满足不满足的情况）减去至少有一种条件不满足的加上有两种的减去有三种的...
证明基于二项式定理，等等吧...

P1450 [HAOI2008] 硬币购物

题意：
- 给出 \(c_{1\sim 4}\)。
- \(Q\) 组询问，每组询问给出 \(num_{1\sim 4}\) 和 \(C\)，求关于 \(a_{1\sim 4}\) 的方程组 \(\sum\limits_{i=1}^4 a_i\times c_i=C\) 的合法解集数。
- 所谓合法解集，即满足 \(\forall i\in [1,4],a_i\in[0,num_i]\) 的解集。
数据范围：\(Q\leqslant 10^3,C\leqslant 10^5\)。
首先显然可以背包，但也同样的，背包显然会 T。
本题有 exgcd 做法，大概思路是预处理 \(c1,c2\) 和 \(c3,c4\) 两组的 \(a_ic_i+a_{i+1}c_{i+1}=\gcd(c_i,c_{i+1})\) 的不定方程，然后对每个询问暴力枚举两组分别付了多少钱，设法 \(O(1)\) 计算方案数。
考虑建立容斥模型：所有方案-有一个超限+有两个超限-有三个超限+有四个超限的方案数。
则问题相当于怎么求有 \(k\) 个超限的方案数。发现此时的选取个数上界变成了选取个数下界；考虑到这个下界肯定 \(\geqslant 0\)，我们用这么一个办法：把它减去！
即，将 \(C\) 减去 \(\sum\limits_{i=1}^4 req_i\times c_i\)，于是问题变成完全背包求方案数。
发现这个完全背包没有必要每次都做，可以预处理。于是得解，复杂度 \(O(4C+2^4Q)\)。
事实上，这一做法可以推广到一般的不定方程非负整数解集计数。

P5664 [CSP-S2019] Emiya 家今天的饭

题意略。
发现这个主要食材的问题看起来就很状压，但 \(m\) 太大了，全无机会。考虑容斥，即爱超不超-至少一种食材超了+...。
发现一种食材如果不合法，其一定占据了至少 \(\lfloor\dfrac{n}{2}\rfloor+1>\dfrac{n}{2}\) 道菜，于是同时至多只有一种食材不合法。
哦吼！那么容易做一个简单 DP \(dp_{i,0/1}\) 表示考虑了前 \(i\) 种烹饪方法，是否已经做过菜的总方案数，从而得出满足前两个条件的总方案数。
然后再暴力枚举超限的食材，做一个 dp 如下：
- 状态设计：\(tp_{i,j,k}\) 表示考虑完前 \(i\) 种烹饪方法，做了 \(j\) 道用这个食材的菜，共做了 \(k\) 道菜的方案数。
- 初始化：\(dp_{0,0,0=1}\)。
- 状态转移方程：\(dp_{i,j,k}=dp_{i-1,j,k}+dp_{i-1,j-1,k-1}\times a_{i,material}+dp_{i-1,j,k-1}\times a_{i,else}\)。滚维即可。
总复杂度 \(O(n^3m)\)，还是超了一些。注意到我们本质上不关心 \(j,k\)，只关心 \([2j>k]\)，换言之关心的是 \([2j-k>0]\)。
起一个偏移，然后把这两维变成一维，总复杂度 \(O(2n^2m)\)，足够通过本题。

P2158 [SDOI2008] 仪仗队

题意：求 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^n [gcd(i,j)=1]\)。这是转化并舍弃了一点细节后的题意。
数据范围：\(n\leqslant 4\times 10^4\)。
式子不是很美妙，考虑拆一拆：

\[\begin{aligned} \sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j) = 1] &=1+\sum\limits_{i=1}^n \sum\limits_{j=1}^{i-1} [\gcd(i,j) = 1]+\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n [\gcd(i,j) = 1] \\ &=1 + 2\times \sum\limits_{i=1}^n \sum\limits_{j=1}^{i-1} [\gcd(i,j) = 1] \\ &= -1 + 2\times \sum\limits_{i=1}^n \varphi(i) \end{aligned} \]

首先利用对称性把它化成可欧拉函数化的式子，然后再代入欧拉函数做变换。一开始 \(+1\) 是因为漏算 \(\gcd(1,1)\)（其他 \(i=j\) 的在变换中直接被舍弃了），最后 \(-1\) 是因为 \(\varphi(1)\) 也计入了并且 \(\times 2\) 了。
众所周知，\(\varphi(i)\) 是可以线性筛的，于是我们有线性复杂度。
什么？没容斥？你别急。

P2398 GCD SUM

题意：求 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^n \gcd(i, j)\)。
这大概算是一个定式。有两种思路：
转化成上面的问题。即：

\[\begin{aligned} \sum\limits_{i=1}^n \sum\limits_{j=1}^n \gcd(i, j) &=\sum\limits_{d=1}^n d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} [\gcd(i,j)=1]\\ &=\sum\limits_{d=1}^n d(-1 + 2\times \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \varphi(i)) \end{aligned} \]

预处理 \(\varphi\) 的前缀和，仍然是线性的。
基于调和级数的暴力：
考虑求 \(div(x)\) 表示 \(\sum\limits_{i=1}^n [x\mid i]\)。此部分的复杂度是 \(O(n)\)。
显然，\(div(x)^2\) 就是所有 \(\gcd\) 为 \(x\) 的倍数的数对的数量。考虑容斥之，可以倒序计算，\(O(n\ln n)\)。
但如果我们用一般的容斥原理，那么实质上是对...总之似乎可以用莫反+狄利克雷前缀和优化到 \(O(n\ln\ln n)\)。

P1447 [NOI2010] 能量采集

题意略。我们约定 \(n\geqslant m\)，若不然，交换之。
首先从 \(\text{P2158 [SDOI2008] 仪仗队}\) 我们知道这种题目显然可以只做对称的两部分中的一部分。
考虑枚举 \(d\)，不妨记 \(k(d)\) 为 \(\gcd\) 为 \(d\) 的数对数量，稍微化下式子有 \(ans=\sum\limits_{d=1}^n (k+1)^2\)。
于是问题变成求 \(\sum\limits_{d=1}^n (\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=d]+1)^2\)。
首先我们还是可以进行一个 \(/d\) 将其转化到 \(\varphi\) 上，但 \(n,m\) 不等使得我们的旧有手段失效了，毕竟对称性完全不存在。
考虑转而多支付一个 \(\log\) 或者之类的。哦，可以容斥！
套用上面的调和级数方法，得解。

P2567 [SCOI2010] 幸运数字

题意略。
暴力求出所有幸运号码，然后开始暴搜容斥。
几个剪枝技巧：
- 若幸运数字中 \(a\mid b\)，删去 \(b\)。
- 由此，我们暴搜中的 \(v\) 应当互相不为倍数；从而对于 \(v\times 3>R\) 的可以直接退出，因为任意 \(lcm\) 至少是 \(v\) 的三倍。

P3160 [CQOI2012] 局部极小值

参看状压 DP。

代表元容斥

子集容斥虽好，但显然有一个致命缺陷：子集总数是指数级的。
当条件很多的时候，其根本没有表现的机会。
代表元容斥给出了一种解决方法：给条件规定一个“顺序”（这一顺序不能违反条件本身的拓扑关系），按顺序考虑这些条件，从而将所有方案分为“违反了第 \(k\) 个条件的”。
换言之，它只关心方案“最早违反的条件”。可以写出如下的一般形式（\(f_{sta}\) 为从初始状态到 \(sta\) 的合法方案数，\(g_{sta,sta'}\) 为从 \(sta\) 到 \(sta'\) 的任意方案数）：

\[f_{sta}=g_{start,sta}-\sum\limits_{sub\subsetneq sta}f_{sub}\times g_{sub,sta} \]

AT_dp_y Grid 2

题意：给出一张 \(n\times m\) 的网格图，有 \(K\) 个点不能经过，求只向下/向右走的条件下（OI 坐标系），从 \((1,1)\) 走到 \((n,m)\) 的方案数。
数据范围：\(n,m\leqslant 10^5,K\leqslant 3\times 10^3\)。
没有不可经过点的话，这是一个经典的组合数学问题。考虑处理这些点，显然子集容斥根本不可做。
注意到对于非法点的访问肯定是有顺序的：\((x,y)\) 成为代表元，即首个访问的非法点，当且仅当所有 \((\leqslant x,\leqslant y)\)（不能同时取等）的非法点都没有访问时，才有可能。
这是一个很松的偏序。随便车一个拓扑序，定义 \(f_{x,y,x',y'}\) 为从 \((x,y)\) 走到 \((x',y')\) 的合法（这里指路上不经过非法点，起止点不算）方案数，\(g_{x,y,x',y'}\) 为对应的任意方案数，于是有：

\[f_{x,y,x',y'}=g_{x,y,x',y'}-\sum\limits_{(x,y)<(x'',y'')<(x',y')} f_{x,y,x'',y''}\times g_{x'',y'',x',y'} \]

这里所有 \((x,y)\) 都是关键点，即 \((1,1),(n,m)\) 或非法点。坐标之间的 \(<\) 是以上面的方式定义的，即 \(x\leqslant x',y\leqslant y'\leftrightarrow (x,y)<(x',y')\)，两个不等号不能同时取等。
于是 \(f_{1,1,n,m}\) 即为所求，复杂度 \(O(K^2)\)。

P2595 [ZJOI2009] 多米诺骨牌

题意略。说实话，其他状压和容斥在它面前都黯然失色。
首先考虑无限制的情况，即，不考虑跨线只考虑障碍。那么这是一个非常板的轮廓线 DP，我们容易做到 \(O(nm2^m)\)。
容易想到把一维用 DP 解决，另一维用容斥。乍一看很对，上面的 DP 也可以加一个 \(0/1\) 辅助维以确保相邻两行能够横跨，然后呢？
不妨记 \(valid_{l,r}\) 为 \(l\sim r\) 列填完，保证合法即每两行之间都有骨牌横跨的方案数。好了，不用说了。
我们看到，这里对列之间的横跨容斥的时候，不管是用子集还是用代表元，都有一个问题：左边的方案自己在行间是合法的，右边也一样，但是考虑不到两者本身不合法拼起来合法的方案。
考虑进一步以退为进，对两维都容斥！先别管 DP，我们假设我们有所有 DP 值，换言之，我们有 \(all_{u,l,d,r}\) 表示子网格 \((u\sim d,l\sim r)\) 的只考虑障碍不考虑横跨的总方案数。
首先肯定不可能都子集容斥，因为时间炸了。考虑使用代表元容斥。
定义 \(f_i\) 表示前 \(i\) 个列间合法，\(g_{i,j}\) 表示 \(i\sim j\) 列的任意方案数，那么...\(f_i=g_{1\sim i+1}-\sum\limits_{j=1}^i f_{j-1}\times g_{j+1,i+1}(f_0=all_{1,1,n,1})\)？
好像是有问题。我们在哪里使得行间合法？
发现好像还是没办法做。如果要记录 \(f_{i,sta}\) 表示 \(sta\) 中的行间已经有骨牌横跨，那就退化成一个 \(dp\) 了，于是没法容斥（容斥怎么可能知道 \(sta\)）。
考虑支付更多复杂度。对列子集容斥，然后强制要求行间合法。
则有 \(ans=\sum\limits_{S=\varnothing}^{full} (-1)^{|S|}\times f_{S,n}\)，\(f_S\) 是在 \(S\) 的条件下（即从 \(S\) 中的位置断开）对行进行代表元容斥的结果。
故发现在某种意义上，子集容斥有比代表元容斥更好的“兼容性”。
最后谈一下 DP 的复杂度分析：暴力枚举左上角和右边界，可以对所有下界一口气求出，总复杂度大约为 \(n^2\sum\limits_{len=1}^n len\times 2^{len}\)，等差乘等比嘛，使劲分析可以证明其收敛，至多 \(4\) 倍常数，考虑到是 \(O\) 且 \(2s\)，较容易过。

标签：gcd,limits,sum,容斥,times,原理,sta
From： https://www.cnblogs.com/weixin2024/p/17053186.html

概述