526互联

[ARC096E] Everything on It 题解

发布时间 2023-08-15 19:25:57作者: User-Unauthorized

题意

对于集合 \({1,2,\cdots,n}\)，求它的子集族中，有多少个满足：

  1. 任意两个子集互不相同；
  2. \(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;
}