题意

求有多少个子集族,满足:
1. 其中任意一个子集都是 $[n]$ 的子集;
2. 任意两个子集互不相同;
3. $1,2,\cdots ,n$ 都在其中至少出现了 $2$ 次。

答案对 $M$ 取模。
$2 \leq N \leq 3000,10^8 \leq M\leq 10^9 +9$,$M$ 是质数。

题解

dyls 说:看到子集族先想到容斥我太菜了
考虑容斥:现在我们是需要数限定一些数只能出现 $0$ 或 $1$ 次,其他数随意出现的方案数。数之间是没有顺序的,所以可以只枚举这样的数的个数,然后计算。令 $g_i$ 表示有 $i$ 个数只能在子集族的元素中出现 $0$ 或 $1$ 次,其他数无限制的方案数,那么答案就是:
$$2^{2^n} - \sum_{i=1}^n (-1)^i \binom n i g_i$$
现在我们考虑如何去算出 $g_i$,一开始的想法可能是去枚举有多少个出现了 $0$ 次,多少个出现了 $1$ 次,然后我们发现我们并不知道有哪些子集可以包含它,但是注意到这题只需要 $O(n^2)$ 的做法,所以我们可以考虑去枚举有多少个子集包含这些数。设有 $j$ 个子集包含了,那么现在的子集族由两部分组成:一部分是子集内全是无限制的数的集合,另一部分是子集内有限制的集合。前一种的贡献显然是 $2^{2^{n-i}}$,后一种的贡献大概就是考虑被限制的数应该被分到这些集合中,但是要注意有些数可以不出现,所以我们可以新建一个集合来表示不出现的数,也就是 $\left \{^{i+1}_ {j+1} \right \}$,然后发现无限制的数也可以加入到这些集合中,所以还有贡献 $(2^{n-i})^j$。
所以 $g_i$ 的计算过程就十分明了了!:
$$g_i = \sum_{j=0}^i 2^{2^{n-i}}\left \{^{i+1}_ {j+1} \right \}(2^{n-i})^j$$
预处理一下卡卡常就过去了。

代码

/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克,只因大师sqy在他背后。不膜大师者违背了真神的旨意,真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-17 14:31:56
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3000+5;
int ha;
int n;
int S[MAXN][MAXN],fac[MAXN],inv[MAXN],facfac[MAXN];

inline int qpow(int a,int n=ha-2,int mod=ha){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%mod;
        a = 1ll*a*a%mod;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    S[0][0] = 1;
    FOR(i,1,MAXN-1){
//        S[i][0] = 1;
        FOR(j,1,i){
            S[i][j] = (S[i-1][j-1]+1ll*j*S[i-1][j]%ha)%ha;
        }
    }
    FOR(i,0,MAXN-1) facfac[i] = qpow(2,qpow(2,i,ha-1));
}

inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    scanf("%d%d",&n,&ha);
    prework();int ans = facfac[n];
    FOR(i,1,n){
        int gx = 0,t1 = 1,b1 = qpow(2,n-i);
        FOR(j,0,i){
            //(gx += 1ll*qpow(2,qpow(2,n-i,ha-1))*qpow(qpow(2,n-i),j)%ha*S[i+1][j+1]%ha) %= ha;
            (gx += 1ll*facfac[n-i]*t1%ha*S[i+1][j+1]%ha) %= ha;
            t1 = 1ll*t1*b1%ha;
        }
        gx = 1ll*gx*C(n,i)%ha;
        if(i&1) gx = ha-gx;
        (ans += gx) %= ha;
    }
    printf("%d\n",ans);
    return 0;
}
Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏