先挖坑,后填坑。
容斥
容斥,实际上就是用总的方案数减去不合法的方案数。
我们考虑以下组合恒等式:
\[\sum_{i = 0}^{n} (-1) ^ {i} C_{n}^{i} = [n = 0]
\]
为什么这个式子跟容斥有关呢?
我们考虑不合法的数量为 \(n\),如果我们计算 \(n\) 的子集并且乘上容斥系数后,你就会发现答案只有在 \(n = 0\) 时有值,所以这个就是对的。
分特产
我们考虑钦定 \(i\) 个人不选特产,其余任意的方案数,这个可以用挡板法解决,所以答案就为:
\[\sum_{i = 0}^{n - 1} (-1)^{i} C_n^i \prod_{j = 1}^m C_{a_j + n - i - 1}^{a_j}
\]
硬币购物
我们先考虑没有硬币的情况,可以发现这个可以直接用多重背包预处理来做。
那么现在加上限制后我们考虑容斥,我们枚举至少集合内不满足条件,那么这个只需要减一减然后再乘个容斥系数就做完了。
[SDOI2013] 方程
我们这里只考虑模数是质数的情况。
首先没有限制是好做的,直接挡板法即可,然后你就会发现第二种限制也是好做的,可以理解为在这个集合内拿走一些数,之后我们在考虑容斥,把第一种限制转换为第二种限制,然后就做完了。
水仙花
我们注意到连续的一段钦定不合法的长度不会超过 \(\log_2 m\) 之后我们预处理一个东西,设 \(pre_{i,j}\) 表示连续不合法长度为 \(i\),结尾为 \(j\) 的方案数,这个是好转移的,之后对于同一长度的求个和,记为 \(sum_i\),目前复杂度 \(O(m \log_2^2 m)\)。
之后我们利用容斥先写出答案的表达式:
\[ans = \sum_{i = 0}^n f(i) \ \ (-1)^i
\]
其中我们设 \(f(i)\) 表示钦定 \(i\) 个不合法方案数,我们上魔法,根据上面的式子设计出来一个 dp,我们设 \(dp_i\) 表示考虑到前 \(i\) 个数的答案,那么就有如下转移:
\[dp_i = \sum_{i = 1}^{\log_2 m} dp_{j - i} \ \ sum_j \ \ (-1)^{j - 1}
\]
之后就没了。
二项式反演
To Be Continued