组合与容斥-题目

CF997C Sky Full of Stars

考虑容斥，假设有 $i$ 行 $j$ 列全部同色的方案数为 $f_{i,j}$，那么最终答案就是：

$$\sum_{i+j>0}\binom{n}{i}\binom{n}{j}\cdot f_{i,j}\cdot (-1)^{i+j+1}$$

考虑表示 $f_{i,j}$，有：

$$f_{i,j}=\begin{cases} 3^{j+n(n-j)}&i=0\\ 3^{i+n(n-i)}&j=0\\ 3^{(n-i)(n-j)+1}&i\not=0,j\not=0 \end{cases}$$

发现 $i=0$ 与 $j=0$ 的情况非常特殊，考虑特殊计算：

$$\sum_{i=1}^n\sum_{j=1}^n\binom{n}{i}\binom{n}{j}\cdot f_{i,j}\cdot(-1)^{i+j+1}+2\sum_{i=1}^n\binom{n}{i}\cdot f_{i,0}\cdot(-1)^{i+1}$$

两个部分分别化简。先看前一半：

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\binom{n}{i}\binom{n}{j}\cdot f_{i,j}\cdot(-1)^{i+j+1}\\ =&\sum_{i=1}^n\sum_{j=1}^n\binom{n}{i}\binom{n}{j}\cdot3^{(n-i)(n-j)+1}\cdot(-1)^{i+j+1}\\ =&\sum_{i=1}^n\sum_{j=1}^n\binom{n}{i}\binom{n}{j}\cdot3^{n^2-ni-nj+ij+1}\cdot(-1)^{i+j+1}\\ =&3^{n^2+1}\cdot (-1)\sum_{i=1}^n\sum_{j=1}^n\binom{n}{i}\binom{n}{j}\cdot3^{-ni}\cdot3^{-nj}\cdot3^{ij}\cdot(-1)^i\cdot(-1)^j\\ =&3^{n^2+1}\cdot (-1)\sum_{i=1}^n\binom{n}{i}\cdot3^{-ni}\cdot(-1)^i\sum_{j=1}^n\binom{n}{j}\cdot3^{(-n+i)j}\cdot(-1)^j\\ =&3^{n^2+1}\cdot (-1)\sum_{i=1}^n\binom{n}{i}\cdot3^{-ni}\cdot(-1)^i\sum_{j=1}^n\binom{n}{j}\cdot(-3^{-n+i})^j\cdot1^{n-j}\\ =&3^{n^2+1}\cdot (-1)\sum_{i=1}^n\binom{n}{i}\cdot3^{-ni}\cdot(-1)^i\cdot((-3^{-n+i}+1)^n-1) \end{aligned}$$

后半部分可以直接算，然后就做完了。

CF1728G Illumination

$m$ 只有 $16$，考虑容斥。先考虑不动态加点如何解决。

我们令 $f(S)$ 表示不覆盖到关键点集合 $S$ 的点灯方案数，则有：

$$ans=\sum_{S\subset U}f(S)\times (-1)^{|S|}$$

这样计算出的 $ans$ 是覆盖了除最左与最右两点之外的所有点但不覆盖最左最右点的方案数，只要加上 $-\infty$ 与 $-\infty$ 两个点即可。

我们考虑如何计算 $f(S)$。不覆盖到关键点集合 $S$ 等价于用 $S$ 中的位置将数轴划分为 $|S|+1$ 个区间，每个区间都不覆盖边界。我们可以 $O(nm^2)$ 预处理出 $g(l,r)$ 表示 $[p_l,p_r]$ 区间内的电灯都不覆盖 $p_l$ 与 $p_r$ 关键点的方案数。 则有：

$$f(S)=\prod\limits_{i=1}^{|S|-1}g(S_i,S_{i+1})$$

所以容斥复杂度为 $O(2^mm)$。

$g$ 数组的处理是平凡的。枚举所有灯 $i$，并枚举所有包含它的区间 $j$。令灯位置为 $a_i$，区间左右端点分别为 $l_j$ 与 $r_j$。则这盏灯的 power 范围是 $[0,\min\{a_i-l_j,r_j-a_i\})$。给 $j$ 的 $g$ 乘上它的贡献即可。复杂度 $O(nm^2)$。

至此，我们 $O(nm^2)-O(2^mm)$ 解决了静态问题。

考虑动态加灯。这盏灯对 $g$ 的修改是可以 $O(m^2)$ 解决的。但是如果每次更改后重新进行容斥，那么复杂度是不能接受的。于是一种方式是在动态加点前算出每个 $g$ 值对答案的贡献，这样单次询问是 $O(m^2)$ 的，可以通过，复杂度 $O(nm^2)-O(2^mm)-O(qm^2)$。

但是有另一种更为简介的方法可以在更优时间复杂度内（单次询问相同，预处理更优）解决此问题。

我们观察到每个容斥状态的值是所有子段值的连乘且所有子段不交且覆盖了区间 $(-\infty,+\infty)$，所以可以将容斥写成 dp 状物，即：

$$dp_i=\sum_{j=1}^{i-1}(-1)\times dp_j\times g(j,i)$$

那么容斥系数在每加一段后都会 $\times -1$，最后就是 $(-1)^{|S|}$。而 $\prod g$ 也在 dp 转移中进行了计算。最后答案为 $dp_{m+1}$。这样单次 dp 复杂度是 $O(m^2)$，可以通过此题。