Solution
容斥，钦定 \(i\) 个数 \(\leq 1\) 次。
\[Ans=\sum_{i=0}^n (-1)^i\binom{n}{i}F(i) \]
其中 \(F(i)\) 表示有 \(i\) 个数的出现次数 \(\leq 1\) 次，剩余 \(n-i\) 个数随意的方案数。
方便起见，不妨设这 \(i\) 个数为 \(1,2,\cdots,i\)。可以把所有子集族中的子集分成两类：
- 含有 \(1,2,\cdots,i\) 中至少一个
- 不含
先考虑第 \(2\) 类。没有任何限制条件，剩余的 \(n-i\) 个数随便选，构成 \(2^{n-i}\) 个子集，每个子集要么选要么不选，那么有 \(2^{2^{n-i}}\) 个子集族。
再来考虑第一类。枚举 \(k\)，表示第一类集合的个数。\(1,2,\cdots,i\) 这 \(i\) 个数要么不出现要么只出现一次，相当于有 \(i\) 个数，分入 \(k\) 个集合，有些数可以不分。考虑再加一个集合（“垃圾堆”），把不分的那些数（即没有出现的数）丢进去。有两种想法，结果是一样的：
- 分“垃圾堆”是否非空讨论，方案数为 \(\begin{Bmatrix}i\\k\end{Bmatrix}+(k+1)\begin{Bmatrix}i\\k+1\end{Bmatrix}\)（前面是所有数都分入集合了的方案数，后面是有些数没有分，乘以 \((k+1)\) 是因为不知道哪个集合是“垃圾堆”）。发现这就是第二类斯特林数的递推式，因此方案数为 \(\begin{Bmatrix}i+1\\k+1\end{Bmatrix}\)。
- 再加入一个 \(0\) 丢到“垃圾堆”，从而使垃圾堆非空，且 \(0\) 所在的就是垃圾堆。方案数为 \(\begin{Bmatrix}i+1\\k+1\end{Bmatrix}\)。
对于第一类的每个集合而言，\(>i\) 的 \(n-i\) 个数可出现可不出现。因此方案数为 \(\begin{Bmatrix}i+1\\k+1\end{Bmatrix}\cdot (2^{n-i})^k\)。
得到：
\[F(i)=\sum_{k=0}^i \begin{Bmatrix}i+1\\k+1\end{Bmatrix}\cdot 2^{(n-i)k}\cdot 2^{2^{n-i}} \]
（枚举的 \(k\) 是第一类集合的个数）
综上：
\[Ans=\sum_{i=0}^n (-1)^i\binom{n}{i}\times \sum_{k=0}^i \begin{Bmatrix}i+1\\k+1\end{Bmatrix}\cdot 2^{(n-i)k}\cdot 2^{2^{n-i}} \]
注意，\(2^{2^{n-i}}\equiv 2^{2^{n-i}\bmod (p-1)}\pmod p\)。
#include<bits/stdc++.h> #define int long long using namespace std; const int N=3e3+5; int n,mod,s[N][N],c[N][N],ans; int mul(int x,int n,int mod){ int ans=mod!=1; for(x%=mod;n;n>>=1,x=x*x%mod) if(n&1) ans=ans*x%mod; return ans; } signed main(){ scanf("%lld%lld",&n,&mod); c[0][0]=1,s[0][0]=1; for(int i=1;i<=n+1;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; s[i][j]=(s[i-1][j]*j%mod+s[i-1][j-1])%mod; } } for(int i=0;i<=n;i++){ int sum=0,p=mul(2,mul(2,n-i,mod-1),mod); for(int k=0;k<=i;k++) sum=(sum+s[i+1][k+1]*mul(2,(n-i)*k,mod)%mod*p)%mod; ans=(ans+(i&1?mod-1:1)*c[n][i]%mod*sum%mod)%mod; } printf("%lld\n",ans); return 0; }