【每日一题】二分图染色

考虑只有一种颜色，对于选取i个节点每边有f[n]= 种
那么两边的话就有ans=f[n]*f[n].这样是有重复的，考虑容斥
结果就是
但是这样复杂度需要n^2

这样就是on递推了

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e7 + 10;
const int mod = 1e9 + 7;

LL mul[maxn];
LL inv[maxn];
LL F[maxn];

void init()
{
    mul[0] = 1;
    for (int i = 1; i < maxn; i++)
        mul[i] = (mul[i - 1] * i) % mod;

    inv[0] = inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i < maxn; i++)
        inv[i] = (inv[i - 1] * inv[i]) % mod;

    F[0] = 1;
    F[1] = 2;
    for (int i = 2; i < maxn; i++)
    {
        F[i] = 2LL * i * F[i - 1] % mod - 1LL * (i - 1) * (i - 1) % mod * F[i - 2] % mod;
        F[i] = (F[i] % mod + mod) % mod;
    }
}

LL C(int n, int m)
{
    return mul[n] * inv[m] % mod * inv[n - m] % mod;
}

LL A(int n, int m)
{
    return mul[n] * inv[n - m] % mod;
}

void solve(int n)
{
    LL ans = 0;
    for (int i = 0; i <= n; i++)
    {
        ans += ((i & 1) ? -1LL : 1LL) * C(n, i) * A(n, i) % mod * F[n - i] % mod * F[n - i] % mod;
        ans = (ans % mod + mod) % mod;
    }
    cout << ans << endl;
}

int main()
{

    init();
    int n;
    while (cin >> n)
        solve(n);
    return 0;
}