bzoj2339: [HNOI2011]卡农

【题意】
　　求出由多少个不同的集合满足下列条件：

　　　　1.集合内含有m个不同的非空数集，每个数集由若干个不同的1~n的数组成。

　　　　2.集合内每个1~n的整数在本集合的所有数集中总共出现偶数次。
　　以上提到的集合和数集均不考虑元素的顺序，即含有的元素相同但元素顺序不同被视为同一种集合。
【题解】
　　还是得强调看了题解，思想很巧妙。。。。
　　直接套式子求出题意所求的集合数是比较困难的。
　　所以考虑补集转化的思想。
　　首先我们把所有元素顺序不同的集合当不同的算，这样会比较容易，只要方案数最后除去m!就是答案了。。。
　　设f[x]为仅需选取x个不同数集就满足条件2的集合数。
　　假设为了满足条件2，那么显然在选取了m-1个不同数集之后，剩下那个数集是确定的。
　　这样就有P(2^n-1,m-1)这样的数集。
　　但这个确定的数集被选取之后可能会不满足条件1。总的有2种情况：
　　　　1.前m-1个集合已满足条件2，使得剩下的数集为空集。（有f[m-1]个这样的集合）
　　　　2.选取的剩下那个数集与之前m-1个的某一个相同。（有f[m-2]*(m-1)*(2^n-1-(m-2))个……）
　　所以我们得减去这2种集合的数量。
　　递推式即为：
　　f[m]=A(2^n-1,m-1)-f[m-1]-f[m-2]*(m-1)*(2^n-1-(m-2))
　　最后只要除以m！就行了。
【代码】

#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
const int mo=1e8+7;
const int N=1000005;
int a,n,m,s,f[N],A[N];
int exp(int x,int k,int p)
{
    int s=1;
    for (;k;x=(ll)x*x%p,k>>=1)
        if (k&1)    s=(ll)s*x%p;
    return s;
}
int inv(int x,int p)
{
    return exp(x,p-2,p);
}
void pre()
{
    a=exp(2,n,mo)-1;
    A[0]=1;
    for (int i=1;i<=m;++i)
        A[i]=(ll)A[i-1]*((a-i+1)+mo)%mo;
}
int main()
{
    cin>>n>>m;    
    pre();
    f[0]=1;f[1]=0;
    for (int i=2;i<=m;++i)    
        f[i]=((A[i-1]-f[i-1]-(ll)f[i-2]*(i-1)%mo*(a-(i-2)+mo)%mo)%mo+mo)%mo;
    s=1;        
    for (int i=1;i<=m;++i)
        s=(ll)s*i%mo;        
    cout<<(ll)f[m]*inv(s,mo)%mo<<endl;
    return 0;
}