容斥原理及证明
最编程
2024-03-26 10:25:53
...
这三个限制可以逐个来解决，然后逐层相乘。
当至少有\(i\)行\(j\)列不染色的且规定为某\(i\)行\(j\)列不染色的时候，设\(f_k\)表示不用\(k\)种颜色的方案。
则：
\[\binom{c}{k}(c-k+1)^{(n-i)(m-j)}=\sum_{t=k}^c \binom{t}{k} f_t
\]
左式的意义为，选\(k\)个颜色不用的方案数。由于还有不涂色的选择，所以并不能保证只有那几个没有用到。假设有一种方案恰好有\(t\)种颜色没用到，根据这样的选择方式，它就被计算了\(\binom{t}{k}\)次。由此得出上式。
二项式反演一下，或者从单纯的容斥角度而言，即可得到：
\[f_k=\sum_{t=k}^c (-1)^{t-k}\binom{t}{k}\binom{c}{t}(c-t+1)^{(n-i)(m-j)}
\]
\[\begin{align*}
\sum_{k=1}^c f_k& =\sum_{k=1}^c \sum_{t=k}^c (-1)^{t-k}\binom{t}{k}\binom{c}{t}(c-t+1)^{(n-i)(m-j)}\\
& =\sum_{t=1}^c \binom{t}{k}\binom{c}{t}(c-t+1)^{(n-i)(m-j)} \sum_{k=1}^t (-1)^{t-k}\binom{t}{k}\\
& =\sum_{t=1}^c \binom{t}{k}\binom{c}{t}(c-t+1)^{(n-i)(m-j)} (-(-1)^t +\sum_{k=0}^t (-1)^{t-k}1^k \binom{t}{k})\\
& =\sum_{t=1}^c (-1)^{t+1}\binom{c}{t}(c-t+1)^{(n-i)(m-j)}\\
\end{align*}\]
合法的方案数即为：
\[(c+1)^{(n-i)(m-j)}-\sum_{k=1}^c f_k=\sum_{k=0}^c (-1)^k\binom{c}{k} (c-k+1)^{(n-i)(m-j)}
\]
这样的方案数，还是会算重，同样因为有不涂色的选择会导致超过\(i\)行或\(j\)列是完全空白的。再进行容斥，即可得到：
\[\begin{align*}
& \sum_{i=0}^n (-1)^i \binom{n}{i}\sum_{j=0}^m (-1)^j \binom{m}{j} \sum_{k=0}^c (-1)^k\binom{c}{k}(c-k+1)^{(n-i)(m-j)}\\
& =\sum_{i=0}^n\sum_{k=0}^c (-1)^{i+k}\binom{n}{i} \binom{c}{k}\sum_{j=0}^m \binom{m}{j}(-1)^j(c-k+1)^{(n-i)(m-j)}\\
& =\sum_{i=0}^n\sum_{k=0}^c (-1)^{i+k}\binom{n}{i} \binom{c}{k}\sum_{j=0}^m [-1+(c-k+1)^{n-i}]^m \\
\end{align*}\]
如果不将后面的求和转化掉的话，复杂度是\(O(n^3)\)。转化后对每一个\(c-k+1\)的幂进行预处理，即可达到\(O(n^2logn)\)的复杂度。
上一篇： 多进程
下一篇： 算法改进：组合数学｜ 排斥原理的常见应用