[ARC096E] Everything on It 题解

题目链接

点击打开链接

题目解法

肯定考虑容斥
钦定有 \(a\) 个数出现 \(0\) 次，有 \(b\) 个数出现恰好 \(1\) 次，其他 \(n-a-b\) 个数随便，容斥系数为 \((-1)^{a+b}\)
先给出方案数的表达式：\(\sum\limits_{a=0}^n\sum\limits_{b=0}^{n-a}(-1)^{a+b}2^{2^{n-a-b}}\binom{n}{a}\binom{n-a}{b}\sum\limits_{c=0}^b {b \brace c}(2^{n-a-b})^c\)
\(\binom{n}{a}\binom{n-a}{b}\) 是 \(n\) 个数分成大小为 \(a,b,n-a-b\) 的堆的方案数
\(2^{2^{n-a-b}}\) 是放任自流的数集任意选
\(c\) 是在枚举那 \(b\) 个数出现在多少个集合中
\({b \brace c}\) 是第二类斯特林数，即 \(b\) 个数分成 \(c\) 的无序集合的方案数
\((2^{n-a-b})^c\) 是指那 \(c\) 个集合可以配上一些放任自流的数的方案数

这样做是 \(O(n^3)\) 的
观察到 \(a+b\) 较为独立，考虑转而枚举 \(s=a+b\)
\(ans=\sum\limits_{s=0}^n(-1)^s 2^{2^{n-s}}\binom{n}{s}\sum\limits_{c=0}^s(2^{n-s})^c\sum\limits_{b=c}^s\binom{s}{b}{b\brace c}\)
从组合意义考虑 \(\sum\limits_{b=c}^s\binom{s}{b}{b\brace c}\)
从 \(n\) 个数中选 \(b\) 个数，放入 \(c\) 的集合（都不能为空）等价于 有 \(n+1\) 个数，放入 \(c+1\) 个集合，最后一个集合代表不选的方案数
这样可以优化到 \(O(n^2)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=3010;
int n,P;
int C[N][N],pw2[N],s2[N][N],PW2[N*N];
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline void dec(int &x,int y){ x-=y;if(x<0) x+=P;}
int main(){
    read(n),read(P);
    F(i,0,n){
        C[i][0]=C[i][i]=1;
        F(j,1,i-1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
    }
    s2[0][0]=1;
    F(i,1,n+1) F(j,1,i) s2[i][j]=(s2[i-1][j-1]+1ll*s2[i-1][j]*j)%P;
    pw2[0]=1;
    F(i,1,n) pw2[i]=pw2[i-1]*2%(P-1);
    PW2[0]=1;
    F(i,1,n*n) PW2[i]=PW2[i-1]*2%P;
    int ans=0;
    F(s,0,n){
        int t=qmi(2,pw2[n-s]);
        F(c,0,s){
            int wys=1ll*C[n][s]*t%P*PW2[(n-s)*c]%P*s2[s+1][c+1]%P;
            if(s&1) dec(ans,wys);
            else inc(ans,wys);
        }
    }
    printf("%d\n",ans);
    return 0;
}