题意:

  • 给你 $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;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code