【题解】AtCoder [ARC096C] Everything on it
bikuhiku
2022-10-19 20:30:49
看到这种计数题，觉得很难正推的，多半是反推，还多半沾点容斥。
***
我们考虑 $dp_i$ 表示有已确定的 $i$ 种元素不合法，其它 $n-i$ 种元素不确定（任意）的方案数，那么可以容斥一下，答案即为：
$$ans = \sum\limits_{i = 0}^{n}(-1)^n \times \binom{n}{i} \times dp_i$$
其中 $\binom{n}{i}$ 就表示从 $n$ 碗面中选择了 $i$ 种。
***
既然 $dp_i$ 中的元素被鲜明地分为了两类，设 $f_i$ 表示确定的 $i$ 种不合法元素的方案数，则有：
$$dp_i = f_i \times 2^{2^{n-i}}$$
其中 $2^{2^{n-i}}$ 意即：$n-i$ 种元素构成了 $2^{n-i}$ 个集合，而这些集合又作为元素构成了 $2^{2^{n-i}}$ 个集合。
注意一下求解 $2^{2^{n-i}}\bmod p$ 请用欧拉定理，变为求解 $2^{2^{n-i}\bmod \varphi(p)}\bmod p$。
***
压力来到了求 $f_i$ 上。我们考虑这 $i$ 个元素分别放到了哪些集合里，设 $g_{i,j}$ 表示 $i$ 个元素放到了 $j$ 个集合里的方案数，则又有：
$$f_i = \sum\limits_{j = 0}^{n}\left(2^{n-i}\right)^{j}\times g_{i,j}$$
即先枚举这 $i$ 个元素放到哪些集合里。
***
怎么求 $g_{i,j}$？可以考虑递推：
$$g_{i,j} = g_{i-1,j-1}+(j+1)\times g_{i-1,j}$$
1. 从 $g_{i-1,j-1}$ 转移：剩下的一种元素必须加到一个新的集合里；
2. 从 $g_{i-1,j}$ 转移：无论把这种元素加到那个集合里、甚至不加入任一个集合都可以。
似乎推组合数、斯特林数时也有类似的式子，也可以说是递推的一个技巧吧。
***
那就开始码代码吧。
```cpp
#include <iostream>
const int N = 3005;
int n, mod;
int C[N][N], g[N][N], ans;
int quick_pow(int _a,int _n,int _p = mod) {
int _res = 1;
while(_n) {
if(_n&1)
_res = 1ll*_res*_a%_p;
_a = 1ll*_a*_a%_p;
_n >>= 1;
}
return _res;
}
int main() {
scanf("%d %d",&n,&mod);
for(int i = 0;i <= n;++i) {
g[i][0] = C[i][0] = 1;
for(int j = 1;j <= i;++j) {
g[i][j] = (g[i-1][j-1]+(j+1LL)*g[i-1][j])%mod;
C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
}
}
for(int i = 0;i <= n;++i) {
int f = 0, pass = 1;
int t_n = quick_pow(2,n-i);
for(int j = 0;j <= i;++j) {
f = (f+1ll*g[i][j]*pass)%mod;
pass = 1ll*pass*t_n%mod;
}
ans = (ans+1ll*f*(i&1 ? mod-C[n][i] : C[n][i])%mod*quick_pow(2,quick_pow(2,n-i,mod-1)))%mod;
}
printf("%d\n",ans);
return 0;
}
```