精讲 组合、容斥
@[TOC]
题目传送

题目：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数，并对10^9^+7取模。 (ps：本题数据量与实际比赛中数据量相比，少了一些)

输入描述:

二分图单边的顶点数目n(n ≤ 10^7)

输出描述:

输出一个整数,即所求的答案。

示例1
输入

2

输出

35

题意&&题解：：

完全二分图:是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。
我们可以把左右各有n个点的二分图的题转化成n*n的棋盘问题。（离散上学过）
题目：让染三个颜色，红蓝绿，但是绿色并没有什么要求，我们可以最后再随便放。所以我们先考虑红和蓝。
红和蓝都是不能共享端点，同步到棋盘上（行和列分别表示二分图两个集合），也就是棋盘上行和列只能有一个红或蓝

现在的题目就是：
在n*n的棋盘上，放任意红和蓝棋子，任一行和列不能有相同颜色的棋子，有多少种放的方法？
Fn表示棋盘大小为 n * n时的答案
先只考虑一个颜色： Fn=在这里插入图片描述)种方案(先在n行里选若干行，然后每一行选若干列，行没有顺序区分，就是选两行，选第一行和第三行与选第一行和第二行没差，所以选行用组合；而列不一样，因为行列只能放一个，我们可以先放在一行上，然后分散到其他行，所以选列的时候要考虑顺序问题，要用的是排列而不是组合)
如图：
在这里插入图片描述
比如我们选两行（C^2^ n ），然后每行放一个，我们先考虑都放在一行上，看图中最上面两行（黄色和绿色），都是选的第一个格和第二个格，但是分散开不一样，（图中4 * 4的表格）说明我们要考虑顺序，所以选列是A^2^n，将所以情况加起来就是选一个颜色的方案

选两个颜色：从上面我们能得到一个颜色是Fn，两个就是Fn* Fn，非也，因为这样会出现一个格子放两个棋子，我们还要将这种情况删去。需要容斥。
我们用gi表示最少有i个点放了两个棋子（颜色不一样）的方案数。那么除去i 行和i 列（i个点所在），我们在剩下n-i行与列里就不会有重复的，gi = f ^2^n-i 。被除去的 i 行与 i列选法和之前一样是 C^i^nA^i^n ，最后得到容斥公式：
在这里插入图片描述
（这一部分好好理解）

C^k^nA^k^n都可以求好，但是Fn提前求会超时，说明上面的公式不能用，我们要换一个想法来求
我们来考虑Fn能不能递推出来，从Fn-1推出Fn
考虑n-1到n的过程：
一共增加了2n-1个格子（n^2^-(n-1)^2^）,n-1之前的格子都已经放好了，我们只需要考虑多出的这些格子该怎么放。
如果只放一个棋子，就有2n-1个方案，如果都不放，一个方案，一共是2n种方案，也就是2nFn-1，（Fn-1是之前n-1行列已经放好的方案数）
但是有限制条件，每一行不能有相同颜色，每放一个棋子，意味着这一行这一列都不能放了，就会出现n-1种重复情况（因为是从n-1的扩展来的），我们之前n-1行列的棋子都平移靠边，因为之前都是不同行同列，所以靠边后，正好占了一行一列，也就是我们在新增部分可以放的棋子，实际上是Fn-2而非Fn-1（这里可以看看图），那一共（n-1）Fn-2次重复情况，可以选n-1行，而且每一列也可以进行相同操作,总的方案数就是2×(n−1) ^2^ ∗F(n−2)
借鉴邓老师的图：
在这里插入图片描述
我们还要考虑放两个的情况;
即最后一行和列分别放一个，这样不重复嘛
方案就是：（n-1）^2^F(n-2)
在这里插入图片描述
总结：得到公式
F[n]=2nF[n-1]-(n-1)^2^F[n-2]
（我真的是把我所能理解都写出来了 ）

代码：

#include<cstdio>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000004;
const int mod = 1e9 + 7;

int g[N],s[N],F[N];
ll C(int n,int m) {
    return 1ll * g[n] * s[m] % mod * s[n - m] % mod;
}
ll A(int n,int m) {
    return 1ll * g[n] * s[n - m] % mod;
}
int main() {
    cin>>n;
    g[0] = 1;
    for(int i = 1;i <= n;++i)
        g[i] = 1ll * g[i - 1] * i % mod;

         ll ans1 = 1;
            for(;y;y >>= 1,x = x * x % mod)
            {
                        if(y & 1) ans1 = ans1 * x % mod;
            }


    s[n] = ans1;



    for(int i = n - 1;i >= 0;--i)
        s[i] = 1ll * s[i + 1] * (i + 1) % mod;

    F[0] = 1;F[1] = 2;
    for(int i = 2;i <= n;++i)
        F[i] = (2ll * i * F[i - 1] - 1ll * F[i - 2] * (i - 1) % mod * (i - 1) % mod) % mod;


    ll ans = 0;
     ll k ;
    for(int i = 0;i <= n;++i) {
       k=1;
        if(i & 1) k = -1;
        ans += k * C(n,i) * A(n,i) % mod * F[n - i] % mod * F[n - i] % mod;
        ans %= mod;
    }
    printf("%lld\n",(ans + mod) % mod);

    return 0;
}