二项式反演
所谓二项式反演，实际上就是一种容斥
我们设满足条件Pi的集合为Ai
那么对于所有的i，都不满足条件P的集合为
[|!A1∩ !A2∩⋯∩ !An|=\|S|−∑|Ai|+∑|Ai∩Aj|+⋯+(−1)^n∑|A1∩A2∩⋯∩An|
]
我们设
[g_i=|A1∩A2∩···Ai|\
g_0=S
]
于是
[|!A1∩ !A2∩⋯∩ !An|=\g_0−C_{n}^{1}g_1+C_{n}^{2}g_2+...+(-1)^nC_{n}^{n}g_n
]
由于左边的项只与个数有关
我们设
[f_i=|!A1∩!A2...∩!Ai|\
f_0=S
]
同理
[|A1∩ A2∩⋯∩ An|=\f_0−C_{n}^{1}f_1+C_{n}^{2}f_2+...+(-1)^nC_{n}^{n}f_n=g_n
]