【题解】Everything on It 容斥 ARC096C —Qiuly

题意：

• 给你 $n$ 种酱。
• 你需要若干碗拉面，并且满足：
  • 你可以在每碗拉面上放若干酱，也可以不放，容易发现方案数为 $O(2^n)$ 。
  • 不能出现放的酱一样的两碗甚至更多拉面。
  • 每一种酱至少在两碗拉面中加了。
• 求拉面集合的方案数。

考虑容斥，设 $S(i)$ 表示有 $i$ 个不合法的酱，其他的 $n-i$ 个酱随意的方案数。那么首先令 $f(i)$ 表示 $i$ 种不合法的酱的方案数，然后显然 $n-i$ 个酱随意的方案数为 $2^{2^{n-i}}$ ，首先 $n-i$ 个酱可选可不选，那么所得的酱集合的方案数为 $2^{n-i}$ ，然后每一种酱集合可选可不选，所以方案数为 $2^{2^{n-i}}$ ，最后从 $n$ 个酱种选出 $i$ 个不合法酱的方案数为 $n\choose i$ 。

现在考虑 $f(i)$ 如何求，设 $g(i,j)$ 表示 $i$ 个不合法酱放到 $j$ 个碗的方案数，可以得到转移：
$$
g(i,j)=g(i-1,j-1)+(j+1)g(i-1,j)
$$
首先对于 $g(i-1,j-1)$ ，意味着第 $j$ 碗酱没有不合法酱，这样就必须将 $i$ 加入到 $j$ 。

然后对于 $(j+1)g(i-1,j)$ ，意味着 $j$ 个碗里面都有不合法酱了，这样的话第 $i$ 个不合法酱可以选择加入到 $j$ 个碗中任意一个，也可以不加入任何碗，所以需要乘上 $j+1$ 。

那么只需要枚举一下到底有几碗加入了不合法酱的面即可：
$$
f(i)=\sum_{j=0}^{i}g(i,j)\times (2^{n-i})^j
$$
$(2^{n-i})^j$ 是因为一碗面中除了不合法酱还可以有其他的酱。

注意 $2^{2^{n-i}}\equiv 2^{2^{n-i}\rm{mod}\ p-1}\ (\rm{mod}\ p)$ 。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=3e3+2;
int n,ans,mod,f[N],g[N][N],C[N][N];

inline int mul(int x,int y) {return 1ll*x*y%mod;}
int modpow(int x,int y,int p,int res=1) {
    for(;y;y>>=1,x=1ll*x*x%p) if(y&1) res=1ll*res*x%p;
    return res;
}
int main() {
    scanf("%d%d",&n,&mod);
    for(int i=0;i<=n;++i) {
        C[i][0]=g[i][0]=1;
        for(int j=1;j<=i;++j) 
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod,
            g[i][j]=(g[i-1][j-1]+mul(j+1,g[i-1][j]))%mod;
    }
    for(int i=0;i<=n;++i) {
        int tmp=modpow(2,modpow(2,n-i,mod-1),mod);
        int num=modpow(2,n-i,mod),qaq=1,res=0;
        for(int j=0;j<=i;++j) res=(res+mul(g[i][j],qaq))%mod,qaq=mul(qaq,num);
        ans=(ans+mul(mul((i&1)?mod-C[n][i]:C[n][i],tmp),res))%mod;
    }
    printf("%d\n",ans);
    return 0;
}