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;
}