Problem C. Let Me Count The Ways Google Kickstart Round H 2018

题意： 有N对couple坐在一排，其中指定的M对newlywed couple中，每个couple不能挨着坐。问一共多少种就坐方式。

结果需要mod 1e7，肯定是个算排列组合数的问题。很容易联想到容斥原理。但是开始纠结容斥原理需要计算所有的子集，总共要算2^N个，肯定会超时。最后半小时才想起来，对于大小相同的子集，他们对应的组合数是一样的，所以每个size只要算一次就行了。然而中途出现了Bug木有时间调了。T^T

令A_i表示couple i (belong to M couples) 坐在一块的方式有几个。那么invalid的坐法个数是 z=|A_0 \cup A_1 \cup ... \cupA_M|，合理的坐法是2^{2N}-z。计算z本质是个集合并集的问题，可以用容斥原理。

以size=n的|A_i \cup...\cup A_j |为例，考虑保证集合中的n个newlywed couple i,..., j是坐一块的，总的组合数是 C(M,n) * C(2*N-n,n) * n! * 2^n * (2*N-n*2)!。其中，C(M,n)是M中size=n的集合的个数。C(2*N-n,n)是从2*N个位置中选出n个2人的位子（两个相邻的位子）放置n个couple，也就等同于2N-n中选择n个位置，每个位置放一个couple。n!是因为集合中的这些newlywed couple之间map到n个位置会有不用的map方式。2^n是每对newlywed couple两个人的位置可以互换。(2*N-n*2)!是安排集合之外的couple的位置，这些couple可能两个人相邻也可能不相邻。

因为公式中仍然可能让n的集合之外的newlywed couple坐一块，所以多加的需要用容斥原理减回来。

开始结果总是出现负数，还以为公式推错了。后来发现a%mod-b%mod这种会导致负数出现，因为取过mod之后，可能前一项比后一项小。应该写成 a%mod+mod-b%mod o(╯□╰)o之前才过很多次坑了，这次又忘了。

桑心，这次题目也没以前难，要是少绕弯子就可以AK了。T_T

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;

//Kickstart Round H Problem C

const int maxn=200010;
int N;
int M;
const int mod=1000000007;
int T;
long long ans;
long long fact[maxn];
long long Pow(long long a,long long b)
{
    long long s=1;
    long long t=1;
    while(b)
    {
        if(b&t)
        {
            s=(s*a)%mod;
        }
        a=(a*a)%mod;
        b=b>>1;
    }
    return s;
}
long long twopow[maxn];
void getfac()
{
    fact[0]=1;
    for(int i=1; i<maxn; i++)
    {
        fact[i]=(fact[i-1]*i)%mod;
//        if(i<5)
//        {
//            cout<<i<<" "<<fact[i]<<endl;
//        }
    }

}

long long inv(long long a) {
    return Pow(a, mod - 2);
}
long long Comb(int n,int m)
{
    if(n==m)
    {
        return 1;
    }
    if(m==0)
    {
        return 1;
    }
    if (n<m)
    {
        return 0;
    }
    return ((fact[n]*inv(fact[m]))%mod*inv(fact[n-m])%mod)%mod;
}
int main()
{

//    freopen("input.txt","r",stdin);
    freopen("C-large-practice.in","r",stdin);
    freopen("C.txt","w",stdout);
    clock_t START_TIME;
    clock_t FINISH_TIME;
    START_TIME=clock();
    scanf("%d",&T);
    memset(fact,0,sizeof(fact));
    getfac();
    memset(twopow,0,sizeof(twopow));
    twopow[0]=1;
    for(int i=1;i<maxn;i++)
    {
        twopow[i]=2*(twopow[i-1]%mod);
        twopow[i]%=mod;
    }
    for(int ca=1;ca<=T;ca++)
    {
        cin>>N>>M;

        N=N*2;
        long long sum=0;
        ans=0;
        int sign=1;
        for(int i=1;i<=M;i++)
        {
            long long tmp=Comb(M,i);
            tmp=tmp*fact[i];
            tmp%=mod;
            tmp=tmp*(Comb(N-i,i))%mod;
            tmp%=mod;
            tmp=tmp*twopow[i]%mod;
            tmp%=mod;
            tmp=tmp*(fact[N-i*2]%mod);
            tmp%=mod;
//            cout<<Comb(M,i)<<" "<<Comb(N-i,i)<<" "<<twopow[i]<<" "<<fact[N-i*2]<<endl;
            if(sign==1)
            {
                sum+=tmp;
            }
            else if(sign==-1)
            {
                sum-=tmp;
            }
            sum%=mod;
            sign=-sign;
//            cout<<"i "<<i<<" "<<tmp<<endl;
        }
        //cout<<N<<" "<<M<<endl;
//        cout<<fact[N]<<" "<<sum<<endl;
        ans=(fact[N]%mod)+mod-(sum%mod);//when there is minus in using mod, remember to +mod, otherwise, negative number may occur
        ans%=mod;
        printf("Case #%d: %lld\n",ca,ans);
        cerr<<"finish case "<<ca<<endl;

    }

    FINISH_TIME=clock();
    cerr<<1.0*(FINISH_TIME-START_TIME)/CLOCKS_PER_SEC <<" (s) "<<endl;
    return 0;
}