[数学记录]AT4119 [ARC096C] Everything on It
command_block
·
·
个人记录
题意 ：
有 n 种酱。你需要若干碗拉面，满足：
你可以在每碗拉面上放若干种酱，也可以不放，容易发现方案数为 O(2^n) 。
不能出现放的酱一样的两碗拉面。每一种酱至少在两碗拉面中加了。
求拉面集合的方案数。答案对给定的质数取模。
------------
进军ATC !
考虑容斥，设 $F(k)$ 表示钦定 $k$ 种酱不合法的方案数。
首先选出不合法的酱，方案书为 $\dbinom{n}{k}$。
首先将 $k$ 种不合法的酱安排到 $i$ 碗拉面中。
设 $g(k,i)$ 为 $k$ 种酱安排到 $i$ 碗拉面，每种都出现最多一次的方案数。
不难联想到一个很类似的数 ： 第二类斯特林数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ ,表示将 $n$ 个球放入无区别的 $m$ 个盒子，所有盒子都非空的方案数。
不同点在于，斯特林数中每个球必须投放一次，而 $g$ 中可以不投放。
考虑新建一个盒子当垃圾桶，但是垃圾桶又只能非空，于是新建一个 $n+1$ 号球，钦定这个球所在的盒子为垃圾桶。
这就能得到 $g(k,i)=\begin{Bmatrix}k+1\\i+1\end{Bmatrix}$。
接下来考虑其他 $n-k$ 种酱料随意选择的方案数。
可以组成 $2^{n-k}$ 种拉面，每种又可以出现或不出现，方案数为 $2^{2^{n-k}}$。
此外，这些酱还能往前面的 $i$ 碗里面加，方案数为 $(2^{n-k})^i$。
答案为 $\sum\limits_{k=0}^n(-1)^kF(k)$ ，即 ：
$$\sum\limits_{k=0}^n(-1)^k\binom{n}{k}2^{2^{n-k}}\sum\limits_{i=0}^k\begin{Bmatrix}k+1\\i+1\end{Bmatrix}(2^{n-k})^i$$
计算幂的幂时需要使用费马小定理。
复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 3050
using namespace std;
int mod,tod;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll pw2[MaxN],s[MaxN][MaxN],fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
pw2[0]=1;
for (int i=1;i<=n;i++)
pw2[i]=pw2[i-1]*2%tod;
s[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
s[i][j]=(s[i-1][j-1]+s[i-1][j]*j)%mod;
}
int n;
int main()
{
scanf("%d%d",&n,&mod);tod=mod-1;
Init(n+1);
ll ans=0;
for (int k=0;k<=n;k++){
ll sav=powM(2,n-k),buf=1,sum=0;
for (int i=0;i<=k;i++){
sum=(sum+s[k+1][i+1]*buf)%mod;
buf=buf*sav%mod;
}sum=sum*C(n,k)%mod*powM(2,pw2[n-k])%mod;
if (k&1)ans-=sum;else ans+=sum;
}printf("%lld",(ans%mod+mod)%mod);
return 0;
}
```