题意
对于集合 \({1,2,\cdots,n}\)，求它的子集族中，有多少个满足：
- 任意两个子集互不相同；
- \(1,2,\cdots,n\) 都在其中至少出现了 \(2\) 次。
\(n \le 3000\)，答案对 \(M\) 取模。
题解
第一个限制形同虚设，下面着重考虑第二个限制。考虑到第二个限制集合的每个元素都是等价的，考虑二项式反演。设 \(f_i\) 为钦定 \(i\) 个元素在子集族中出现次数小于等于 \(1\) 的方案数，\(g_i\) 为有且仅有 \(i\) 个元素在子集族中出现次数小于等于 \(1\) 的方案数。那么可得
\[\begin{aligned} f_i &= \sum\limits_{j = i}^n \dbinom{j}{i} g_j \\ g_i &= \sum\limits_{j = i}^n \left(-1\right)^{j - i}\dbinom{j}{i}f_j \end{aligned}\]发现题目要求的其实就是 \(g_0\)，即
\[\sum\limits_{i = 0}^{n} \left(-1\right)^{i}f_i \]下面考虑如何计算 \(f_i\)。
我们考虑钦定的过程，显然这部分有 \(\dbinom{n}{i}\) 种方案。对于钦定的 \(i\) 个元素，可以分为两类：出现一次的和没有出现的。对于没有出现过的元素可以不考虑，对于只出现一次的元素，设其个数为 \(j\)，可以考虑将其划分为若干集合，然后再与未钦定的元素进行搭配。将相互区分的 \(n\) 个元素划分为 \(k\) 个不互相区分的非空集合方案数为 \(\displaystyle{n \brace k}\)，即第二类斯特林数。所以将钦定的 \(i\) 个元素选取 \(j\) 个并划分为 \(k\) 个集合的方案数为 \(\displaystyle \dbinom{i}{j} {j \brace k}\)。接下来我们考虑剩余的元素，这些元素没有被限制，可以出现一次、多次或不出现，所以剩余的 \(n - i\) 个元素在一个含有钦定元素的集合中共有 \(2^{n - i}\) 种分配方式，因为含有钦定元素的共有 \(k\) 个子集，所以根据乘法原理可得使得在已钦定 \(i\) 个元素的情况下，均含有钦定元素且钦定元素最多出现一次的子集族有 \(\displaystyle\sum\limits_k 2^{\left(n - i\right)k} \sum\limits_j \dbinom{i}{j} {j \brace k}\) 种。接下来考虑不含有钦定的 \(i\) 个元素的子集族，可以发现共有 \(\displaystyle 2^{n - i}\) 种子集，均在子集族中可以独立地出现或不出现，这部分的方案数为 \(\displaystyle2^{2^{n - i}}\)。根据乘法原理，将钦定 \(i\) 个元素的方案数、含有钦定元素且钦定元素最多出现一次的子集族数、不含有钦定元素的子集族数相乘即可得到 \(f_i\) 的表达式。
\[\displaystyle f_i = \dbinom{n}{i}\sum\limits_k 2^{\left(n - i\right)k}\sum\limits_j\dbinom{i}{j}{j \brace k} 2^{2^{n - i}} \]代入我们上面的式子中，可以得到答案的表达式
\[\begin{aligned} Ans &= \sum\limits_{i = 0}^{n} \left(-1\right)^{i}\dbinom{n}{i}\sum\limits_{k = 0}^{i} 2^{\left(n - i\right)k}\sum\limits_{j = k}^{i}\dbinom{i}{j}{j \brace k} 2^{2^{n - i}} \\ &= \sum\limits_{i = 0}^{n} \left(-1\right)^{i}\dbinom{n}{i}2^{2^{n - i}}\sum\limits_{k = 0}^{i} 2^{\left(n - i\right)k}\sum\limits_{j = k}^{i}\dbinom{i}{j}{j \brace k} \end{aligned}\]我们设 \(\displaystyle g_{i,k} = \sum\limits_{j = k}^{i}\dbinom{i}{j}{j \brace k}\)，考虑如何处理出这个算式，考虑其组合意义，可以发现为在 \(i\) 个元素中选取若干个元素划分为 \(k\) 个非空集合的方案数。我们在这 \(i\) 个元素中再添加一个元素，将没有被选取的元素和这个添加的元素划分到一个新的集合，所以可得总方案数为 \(\displaystyle{i + 1 \brace k + 1}\)，不难看出其递推式为 \(\displaystyle g_{i, k} = g_{i - 1, k - 1} + \left(k + 1\right)g_{i - 1, k}\)。递推地计算出所有需要的 \(g_{i, k}\) 值再按照表达式计算即可以 \(\mathcal{O}(n^2)\) 的复杂度通过本题。
Code
//AT_agc096_c
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
valueType MOD_;
valueType const &MOD = MOD_;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, const T2 &b, const T3 &mod = MOD) {
a = a + b;
if (a > mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, const T2 &b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(const T1 &a, const T2 &b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(const T1 &a, const T2 &b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(const T1 &a, const T2 &b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, const T2 &b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 Pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
class Inverse {
public:
typedef ValueVector container;
private:
valueType size;
container data;
public:
explicit Inverse(valueType n) : size(n), data(size + 1, 0) {
data[1] = 1;
for (valueType i = 2; i <= size; ++i)
data[i] = mul((MOD - MOD / i), data[MOD % i]);
}
valueType operator()(valueType n) const {
return data[n];
}
};
int main() {
valueType N;
std::cin >> N >> MOD_;
Inverse Inv(N);
ValueVector Fact(N + 1, 1), InvFact(N + 1, 1);
Fact[0] = 1;
InvFact[0] = 1;
for (valueType i = 1; i <= N; ++i) {
Fact[i] = mul(Fact[i - 1], i);
InvFact[i] = mul(InvFact[i - 1], Inv(i));
}
typedef std::function<valueType(valueType, valueType)> CalcFunction;
CalcFunction C = [&Fact, &InvFact](valueType n, valueType m) -> valueType {
if (n < 0 || m < 0 || n < m)
return 0;
return mul(Fact[n], mul(InvFact[m], InvFact[n - m]));
};
ValueMatrix G(N + 1, ValueVector(N + 1, 0));
G[0][0] = 1;
for (valueType i = 1; i <= N; ++i) {
G[i][0] = 1;
for (valueType j = 1; j <= N; ++j)
G[i][j] = sum(mul(j + 1, G[i - 1][j]), G[i - 1][j - 1]);
}
valueType ans = 0;
for (valueType i = 0; i <= N; ++i) {
valueType const Pow2 = mul(Pow(2, Pow(2, N - i, MOD - 1), MOD), C(N, i));
valueType const pre = (i & 1 ? MOD - Pow2 : Pow2);
valueType const PowN = Pow(2, N - i, MOD);
valueType PowJ = 1;
for (valueType j = 0; j <= i; ++j, Mul(PowJ, PowN))
Inc(ans, mul(pre, mul(PowJ, G[i][j])));
}
std::cout << ans << std::endl;
return 0;
}