Luogu

BZOJ

分析

这题真的神仙。

转换一下题意:从集合$\{1,2,...,n\}$中无序地选出$m$个互不相同的非空子集,要求在这些选出的子集中,每个数出现次数为偶数。求方案数。

首先,把无序转为有序,并将最后答案除以$m!$。

设$f[i]$表示选出$i$个满足所有限制的子集的方案数。

很难得出状态转移方程:$\large f[i]=A_{2^n-1}^{i-1}-f[i-1]-\Bigg\{f[i-2]\times(i-1)\times\left[2^n-1-(i-2)\right]\Bigg\}$。

详细的解释戳这里

最后,边界是$f[0]=1,f[1]=0$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;
const int MOD=100000007;

inline int FastPow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=a*a%MOD)
        if (b&1) ans=ans*a%MOD;
    return ans;
}

int A[MAXN],f[MAXN];

mainint main() {
    int n=read(),m=read(),p=FastPow(2,n)-1; //p=2^n-1
    f[0]=1,f[1]=0,A[0]=1;
    for (re int i=1;i<=m;++i) A[i]=A[i-1]*(p-i+1)%MOD;
    for (re int i=2;i<=m;++i) {
        f[i]=A[i-1]-f[i-1]-(f[i-2]*(i-1)%MOD*(p-(i-2))%MOD);
        f[i]=(f[i]+MOD)%MOD;
    }
    int inv=1;
    for (re int i=1;i<=m;++i) inv=inv*i%MOD;
    inv=FastPow(inv,MOD-2);
    printf("%lld\n",f[m]*inv%MOD);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 53 PM