zoj 3688 The Review Plan II(容斥原理+禁位排列+逆元)

一时失言乱红尘 2022-06-10 11:53 108阅读 0赞

##                                 The Review Plan II      ##

Michael is very grateful for your last help of his review plan. Now he finds that it's interesting to do the review in a different way than ordinary students, he wants you to help him again.

The whole book he needs to review has N chapters, he wants to arrange exactly Ndays to take his review, and one chapter by each day.

But he does not want to read the ith(1 ≤ i ≤ N\-1) chapter in the ith day or the(i+1)th day. And read the Nth chapter in the Nth day or in the first day is not acceptable too. Can you tell him how many different appropriate plans he could make ?

Input

There are multiple test cases. For each test case there is a single line contains one integer N(1 ≤ N ≤ 100000), N is the number of the days and also the number of the chapters in the book.

Process to the end of input.

Output

One line for each case. The number of the different appropriate plans module 1000000007.

Sample Input

2
    4

Sample Output

0
    2

Hint

For case 1, there is no such plan. For case 2, you can arrange the plan as (2, 3, 4, 1) or (3, 4, 1, 2).

题意：一本书有N章，第一章不能在第一天和第二天看，第二章不能在第二天和第三天看，第n章不能在第n天和第n+1天看，最后一章不能在最后一天和第一天看，问有多少种看的方式。

思路：这是一道禁位排列的题目。我们可以把棋盘多项式画出来

当N=6的时候：![Center][]![Center 1][]

仔细观察我们可以发现：1，2不能同时出现，2，3不能同时出现，3，4不能同时出现，所以当我们找错排情况的种数的时候，可以看作是在找一个长为2N的圆，选择k个不相邻的点的方法。在张坤龙的组合数学讲义里有一个定理，如下。

![Center 2][]

然后我们只需要再根据容斥原理，k为奇数时ans-=v，k为偶数时ans+=v，（v就是长为2N的圆，选择k个不相邻的点对应的方案数），答案就出来了。在算组合数的时候需要用一下逆元的知识，因为模的是1e9+7，是素数，所以我们可以用费马小定理求逆元。AC代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")
    #include <stdio.h>
    #include <queue>
    #include <map>
    #include <vector>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <cstdlib>
    #include <cctype>
    #include <set>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int MOD = 1e9 + 7;
    const int MAXN = 2e5 + 10;
    ll f[MAXN];
    ll mod_pow(ll a, ll n)
    {
    	ll ans = 1;
    	while (n)
    	{
    		if (n & 1) ans = ans*a%MOD;
    		a = a*a%MOD;
    		n >>= 1;
    	}
    	return ans;
    }
    
    void init()
    {
    	f[0] = 1;
    	for (int i = 1; i<MAXN; i++)
    		f[i] = (i*f[i - 1]) % MOD;
    }
    
    
    int main()
    {
    	//freopen("in","r",stdin);
    	init();
    	int n;
    	while (cin >> n)
    	{
    		ll ans = f[n];
    		for (int i = 1; i <= n; i++)
    		{
    			ll v = f[2 * n - i - 1] * mod_pow(f[i - 1], MOD - 2) % MOD;
    			v = v*mod_pow(f[2 * n - 2 * i], MOD - 2) % MOD;
    			v = v * 2 * n%MOD;
    			v = v*mod_pow(i, MOD - 2) % MOD;
    			v = v*f[n - i] % MOD;
    			if (i % 2 == 0) ans = (ans + v) % MOD;
    			else ans = (ans - v + MOD) % MOD;
    		}
    		if (n == 1) ans = 0;
    		cout << ans << endl;
    	}
    	return 0;
    }

[Center]: https://img-blog.csdn.net/20170818135702426?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQva2VsZTUyaGU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220610/98e2bae480944b70a16a4eea2ec5cf66.png
[Center 2]: /images/20220610/c46afcfc77ba4e96b7f64e4c16be2848.png