这种题在想题的时候可以先随便找到一个做法再去优化，不要管复杂度，想多了容易混。
首先容易发现，这道题直接计数比较困难。所以我们想到了用容斥来解决这个问题。
但是容斥的方式可能比较多，可以多尝试然后选择最简便的方法。钦定 \(f_i\) 表示，我们强制 \(n\) 个数中的 \(i\) 个出现次数不超过 \(1\) 的数。那么答案即为下式：
\[\sum_{i=0}^n (-1)^i\binom{n}{i}f_i \]现在的问题就是怎么求 \(f_i\)。我们先算这 \(i\) 个数的方案数，考虑强制其中一些数恰好出现一次，且枚举一个 \(j\) 表示我们要把强制选的数分进这 \(j\) 个组（剩下不强制的数可以分进某一组也可以不选），那么方案数易得：\(i+1\brace j+1\)。因为我们可以把那些不选的单独看成一个组，然后为了防止这个组别里没有人而出现少算，我们另外钦定一个 \(i+1\) 号节点来代表这个组。
最终的 \(f_i\) 还要算上剩下 \(n-i\) 个数的方案数。剩下的数可以组成的集合数为 \(2^{n-i}\)，方案数为 \(2^{2^{n-i}}\)（对于每个集合都有选与不选两种情况）。此外，剩下的数还可以放入原来的集合，故而方案数为 \((2^{n-i})^j\)。
时间复杂度 \(O(n^2)\)，可以通过。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
constexpr int N = 3e3 + 10;
int n, mod, ans, C[N][N], S[N][N];
int Qpow(int a, int b, int P = mod){
int ans = 1;
while(b){
if(b & 1) ans = (ll)ans * a % P;
a = (ll)a * a % P, b >>= 1;
}
return ans;
}
int Inv(int x){
return Qpow(x, mod - 2);
}
void Init(){
FL(i, 1, n + 1){
S[i][1] = 1;
FL(j, 2, i){
S[i][j] = (S[i - 1][j - 1] + (ll)j * S[i - 1][j]) % mod;
}
}
FL(i, 0, n){
C[i][0] = 1;
FL(j, 1, i){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
void Calc(){
FL(i, 0, n){
int c = (i & 1? mod - 1ll : 1ll) * C[n][i] % mod;
c = (ll)c * Qpow(2, Qpow(2, n - i, mod - 1)) % mod;
FL(j, 0, i){
ans = (ans + (ll)c * S[i + 1][j + 1] % mod * Qpow(2, (ll)(n - i) * j % (mod - 1))) % mod;
}
}
}
int main(){
scanf("%d%d", &n, &mod);
Init(), Calc();
printf("%d\n", ans);
return 0;
}