BZOJ2839:集合计数(容斥,组合数学)

这个问题是一个比较经典的容斥原理的应用题目。我们可以考虑使用容斥原理来求解这个问题。具体来说，我们可以考虑求出所有集合的个数，然后减去至少包含一个特定元素的集合的个数，再加上至少包含两个特定元素的集合的个数，以此类推，直到加上包含所有特定元素的集合的个数。

对于一个大小为n的集合，其子集的个数为2^n。因此，所有集合的个数为2^n。现在我们考虑如何计算至少包含一个特定元素的集合的个数。我们可以将这个特定元素看作是一个元素，然后考虑其余n-1个元素组成的集合的个数，即2^(n-1)。因此，至少包含一个特定元素的集合的个数为2^(n-1)。同理，至少包含两个特定元素的集合的个数为C(2,n)*2^(n-2)，其中C(2,n)表示从n个元素中选取2个元素的组合数。

将以上结果代入容斥原理的公式中，即可得到最终的计数公式：
sum((-1)^k*C(k,n)*2^(n-k),k=0,1,...,n)

其中，sum表示对k从0到n进行求和，C(k,n)表示从n个元素中选取k个元素的组合数，2^(n-k)表示剩余元素组成集合的个数。

相关问题

BZOJ2194: 快速傅立叶之二 (FFT)

这是一道经典的FFT模板题目，需要你掌握FFT的基本原理和实现。

FFT（快速傅里叶变换）是一种用于计算离散傅里叶变换（DFT）的算法。它将DFT的时间复杂度从O(N^2)降低到了O(N*logN)，因此在处理大规模数据时具有很高的效率。

对于这道题目，你需要计算两个多项式的乘积。可以将这两个多项式看作是两个长度为N的序列A和B，然后使用FFT算法计算它们的卷积，即C[i] = A[i]*B[i]，最后再使用逆FFT将C转化为多项式形式即可。

具体实现方面，可以使用递归实现FFT算法，也可以使用迭代实现。递归实现的代码比较简洁，但在处理大规模数据时可能会出现栈溢出的问题。迭代实现则可以避免这种问题，但代码会稍微复杂一些。

如果你还没有掌握FFT的基本原理和实现，建议先去学习一下。推荐的学习资源包括CLRS算法书籍、博客文章和相关视频教程。

BZOJ2179: FFT快速傅立叶 FFT实现高精度乘法

这道题目是要求用 FFT 实现高精度乘法。我们可以先将两个高精度数转换为多项式，然后对这两个多项式进行相乘，最后将结果转换为高精度数输出即可。

具体来说，将两个高精度数 $a$ 和 $b$ 分别转换为多项式 $A(x)$ 和 $B(x)$：

$$
A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} \\
B(x) = b_0 + b_1x + b_2x^2 + \cdots + b_{n-1}x^{n-1}
$$

其中 $n$ 是 $a$ 和 $b$ 的位数，为了方便计算，我们要将 $n$ 扩展到 $2^k$，并在低位补 0。即：

$$
A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} + 0x^n + \cdots + 0x^{2^k-1} \\
B(x) = b_0 + b_1x + b_2x^2 + \cdots + b_{n-1}x^{n-1} + 0x^n + \cdots + 0x^{2^k-1}
$$

接下来我们需要用 FFT 对 $A(x)$ 和 $B(x)$ 进行多项式乘法，得到多项式 $C(x) = A(x) \times B(x)$。然后将 $C(x)$ 转换为高精度数输出即可。

注意，由于 FFT 实现的是循环卷积，而我们要求的是线性卷积，因此在进行 FFT 前需要对 $A(x)$ 和 $B(x)$ 进行点值扩展，即令 $A'(x) = A(x) \times x^k$，$B'(x) = B(x) \times x^k$，其中 $k = 2^k - n$。这样得到的 $C'(x) = A'(x) \times B'(x)$ 在进行 FFT 后，其前 $n$ 项即为 $C(x)$ 的系数项，可以直接转换为高精度数输出。

代码实现如下：