一些 trick (5) | 如何更好地计算容斥？

· · 算法·理论

例题 1. CF1530F

题意：给 n 行 n 列的网格染色，第 i 行第 j 列的格子有 p_{i,j} 的概率染黑，否则染白，且彼此独立，求 n 行 n 列和两条对角线至少有一条线被完全染黑的概率。

考虑容斥。钦定一些行、列、对角线是黑的计算概率是 $O(4^nn^2)$ 的，无法通过。 注意到已经钦定好行、对角线来说，钦定一些列的贡献可以写成 $c\prod\limits_{i\in S}f_i$ 的形式，那么显然这项的答案就是 $c\prod\limits_{i=1}^n(1-f_i)$，统计 $f_i$ 可以直接 $O(n^2)$ 暴力做，时间复杂度 $O(2^nn^2)$。 例题 2. [TopCoder 12607](https://community.topcoder.com/stat?c=problem_statement&pm=12607) 题意：给 $n$ 行 $m$ 列初始全为白的网格染色，每次以 $\dfrac{a_{i,j}}{\sum\limits_{i'j'}a_{i',j'}}$ 的概率给第 $i$ 行第 $j$ 列的格子染黑（如果被染过则不然，但计入操作次数）。求每行每列至少有一个格子染黑的期望次数。保证答案存在。 $n,m\le 21,nm\le 150,a_{i,j}\le 9$ 为整数。 令 $s=\sum a_{i,j}$。考虑每行每列都有的次数就是它们的 $\max$。考虑 $\min-\max$ 容斥，则答案可以写成 $E[\sum\limits_{I\subseteq[1,n],J\subseteq[1,m],|I|+|J|>0}(-1)^{|I|+|J|-1}\dfrac{s}{s-\left(\sum\limits_{i\not\in I,j\not\in J}a_{i,j}\right)}]$。（熟知做一件成功率为 $p$ 的事期望需要 $\dfrac{1}{p}$ 次） 不妨设 $n\le m$，那么有 $n\le 12$。考虑枚举 $I$，那么括号里的式子可以写成 $\sum_{j\not\in J}f_j$，直接背包（系数乘 $-1$）计算即可。时间复杂度 $O(2^{\min(n,m)}s\max(n,m))$。 已经加入 [一些 trick](https://www.luogu.com.cn/blog/483824/some-tricks)。