容斥原理

wjh15101051's space

卧薪尝胆，厚积薄发。

容斥原理

Date: Wed Feb 27 23:18:26 CST 2019

In Category: 总结

容斥系数：

一般也就几种：组合数，斯特林数，莫比乌斯函数。

可能还会有 $(-1)^x$ 或者阶乘作为系数。

两种在容斥系数不显然的情况下构造容斥系数的方法：

一：打表法：设 $f[i]$ 表示容斥系数，然后一般会有一个 $f$ 的和式最后等于 $[i满足某种条件]$ ，即如果满足某种条件，就加一，然后可以依次让这个式子在 $i=1,2,\dots$ 时成立，然后就可以递推 $f$ 了，一般是 $O(n^2)$ 的。

二：反演法：

一般会有这样一个式子： $$ g[i]=\sum_k a_{i,k}f[k] $$ 然后我们想求一个系数 $b_{i,j}$ ： $$ f[i]=\sum_kb_{i,k}g[k] $$ 那么我们就可以强行带入： $$ g[i]=\sum_j a_{i,j}\sum_kb_{j,k}g[k] $$ 也就是说： $$ \sum_ja_{i,j}b_{j,k}=[i=k] $$ 然后我们就可以这样去构造 $b$ 。

In tag:

wjh15101051