[JZOJ3466] 選課

Description

你真的認為選課是那麼容易的事嗎？HYSBZ的ZY同志告訴你，原來選課也會讓人産生一種想要回到火星的感覺。

假設你的一周有n天，那麼ZY編寫的選課系統就會給你n堂課。但是該系統不允許在星期i和星期i+1的時候選第i堂課，也不允許你在星期n和星期一的時候選第n堂課。然後連你自己也搞不清哪種選課方案合法，哪種選課不合法了。你隻想知道，你到底有多少種合法的選課方案。

答案mod 109+7

Solution

這是一道。。。。額好吧，這是一道結論題

許多人說過，正難則反（十分顯然我并沒有貫徹落實這一思想）

So ⋯

設 W(k) 表示至少有 k 門課是不合法的方案數

搞出來W(k)以後就是裸的容斥原理了

然而， W 怎麼求呢

把每堂課不合法的天數寫出來（也就是W中要選的）

(1,2)(2,3)(3,4)(4,5)⋯(N,1)

把括号去掉排成一個長為 2N 序列

然後我們要從中選出 k 個括号，其中每個括号選一個數，代表這k節課的日期

并且要滿足

• 第 2i 項和第 2i+1 項（也就是相鄰兩個括号相鄰的兩個數）不可以同時選，因為同一天不能有兩節課
• 第 2i 項和第 2i−1 項（也就是一個括号中的兩個數）不可以同時選，因為一個括号代表一門課，一門課不可以上兩天

兩個條件合并，就是

• 相鄰兩項不能同時選！！

給你 2N 個點的環（因為首尾相接），求不能選相鄰兩個點的選 k 個點的方案數

先考慮一個序列的情況

我們選了k個點，那麼要使兩個點之間至少有一個點沒選

我們是不是可以想，把這些點删去，是不是就可以任意選了？

原問題就變成了在 2N−k+1 個點中選 k 個，然後把剩下k−1個在每兩個之間放進去就合法了。

是以這樣選的方案數是 Ck2N−k+1

考慮環

破環為鍊

然後我們顯然可以像在序列中那樣，在第一個選前面的和最後一個選後面這段中的删掉一個

于是就變成了 Ck2N−k

然後破環的方式有 2N 種，是以還要乘個 2N

完了，嗎？

因為乘了 2N 以後，每種選法中的 2N−k 個點都有可能成為破環的那個點

是以多乘了 2N−k ，這一部分要除掉

剩下的 N−k 門課可以亂選了。

W(k)=Ck2N−k×2N2N−k×(N−k)!

化簡公式

W(k)=(2N−k−1)!(N−k)!2Nk!(2N−2k)!

注意要預處理階乘和逆元

Code

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define mo 1000000007
#define LL long long
using namespace std;
int n;
LL js[],ny[],ny1[];
LL ksm(LL k,LL n)
{
    LL s;
    if (n==) return(k);
    s=ksm(k,n/);
    if (n%2==)return(s*s%mo);
    else return(s*s%mo*k%mo);
}
int main()
{
    freopen("select.in","r",stdin);
    int i;
    js[]=;
    LL x,y;
    fo(i,,) 
    {
        js[i]=(i*js[i-])%mo;
        ny[i]=ksm(js[i],mo-);
    }
    ny[]=;
    while (scanf("%d",&n)!=EOF)
    {
        if (n<=) printf("0\n");
        else
        {
            LL ans=js[n],j=-;
            fo(i,,n) 
            {
                ans=(ans+j*js[n-i]*2*n%mo%mo*js[*n-i-]%mo*ny[i]%mo*ny[*n-*i]%mo+mo)%mo;
                j=-j;
            }
            printf("%lld\n",ans);
        }
    }
}