组合数学——P3214 [HNOI2011]卡农

joe19025 · 2019-03-25 19:07:29 · 题解

Solution

抽象问题

对于集合 \{1,2,3,4,5,6,7…,n\}，

从上述集合中选取m个子集，且需要满足以下要求。

性质：

1. 每个集合非空。
2. 任意两个集合互不相同。
3. 每一个元素在这m个集合中出现偶数次。

计算方式

我们需要算的是集合的组合，但相比来说排列更好算，所以先算排列，最后除 m! 即可。

我们定义 f[i] 为选择i个集合，且满足上面三个条件的方案数。

• 由于已知前 i-1 个集合的信息，根据性质3，第 i 个集合已经确定了，所以总共有 A_{2^n-1}^{i-1} 种。
• 由于性质1，第 i 个集合非空。所以如果前 i-1 个满足上述性质，则第i个不满足上述性质。所以根据容斥原理，需要减掉 f[i-1] 。
• 由于性质2，我们需要保证第 i 个集合和前面的互不相同。假设第 i 个集合和第 j 个集合相同，j 可能是第1个到第  i-1个集合中任意一个，共有i-1种可能性。由于满足性质3，所以剩下的 i-2 个集合也满足性质3，所以他们共有 f[i-2] 种方案。而对于相同的两个集合，我们需要它和之前的i-2个集合不相同即可，共有 2^n-1-(i-2) 种。综上，需要减去 (i-1)\times f[i-2]\times(2^n-i+1)。

得出结论： f[i]=A_{2^n-1}^{i-1}-f[i-1]-(i-1)\times f[i-2]\times(2^n-i+1)

复杂度 O(n)

每一次转移 O(1) 。

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#define int long long
#define MAXN 1000005
using namespace std;

const int mod=100000007;

int qpow(int x,int k)
{
    int res=1;
    while(k>0)
    {
        if(k&1)
            res=res*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return res;
}

int inv(int x)
{
    return qpow(x,mod-2);
}

int n,m,A[MAXN],f[MAXN];

signed main()
{
    cin>>n>>m;
    A[0]=1;
    int mx=(qpow(2,n)-1)%mod;
    for(int i=1;i<=m;i++)
        A[i]=A[i-1]*((mx-i+1+mod)%mod)%mod;
    f[0]=1;
    for(int i=2;i<=m;i++)
    {
        f[i]=(A[i-1]-f[i-1]+mod)%mod;
        f[i]=(f[i]-f[i-2]*(mx-i+2)%mod*(i-1)%mod+mod)%mod;
    }
    int frac=1;
    for(int i=1;i<=m;i++)frac=frac*i%mod;
    cout<<f[m]*qpow(frac,mod-2)%mod;
    return 0;
}