NC19857 - 最后的晚餐

题意

给你一个圆桌，这个圆桌有个位置，现在有对情侣要入座，问你有多少种方案使得所有情侣都不相邻

数据范围

思路

我们定义性质表示第对情侣相邻， 那么这个题的答案就是

那么根据容斥原理可得:

因为每对情侣的情况是一样的，假设有对情侣相邻，那么方案数就是

那么最终的答案就是:

Notes: 个人圆排列方案数:

代码

/**
 *    author: andif
 *    created: 28.08.2023 23:51:46
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 3e7 + 1;
int inv[N];

int kpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = 1ll * ret * a % mod;
        }
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ret;
}

int gao(int x) {
    int ret = 1;
    rep(i, 1, x + 1) ret = 1ll * ret * i % mod;
    return ret;
}

int main() {
    qc;
    int n; cin >> n;
    if (n == 1) return cout << "0" << '\n', 0;
    int fn = 1, pn = 1;
    rep(i, 1, n + 1) {
        fn = 1ll * pn * i % mod;
        if (i != n) pn = fn;
    }
    // dd(fn), de(pn);
    inv[n] = kpow(fn, mod - 2);
    per(i, n - 1, -1) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    // rep(i, 1, n + 1) if(1ll * inv[i] * gao(i) % mod == 1) de(i);
    int p2 = kpow(2, n), inv2 = kpow(2, mod - 2);
    int ans = 1ll * pn * p2 % mod;
    if (n & 1) ans = -ans + mod;
    // de(ans - mod);
    per(i, n - 1, -1) {
        int fg = i & 1 ? -1 : 1;
        int cur = 1ll * pn * (2 * n - i - 1) % mod;
        p2 = 1ll * p2 * inv2 % mod;
        // dd(fg), dd(1ll * fn * inv[n - i] % mod * inv[i] % mod), dd(cur), dd(p2);
        // int tmp = 1ll * fn * inv[n - i] % mod * inv[i] % mod * cur % mod * p2 % mod;
        // de(tmp);
        ans = (ans + fg * 1ll * fn * inv[n - i] % mod * inv[i] % mod * cur % mod * p2 % mod) % mod;
        pn = cur;
        // de(ans);
    }
    if (ans < 0) ans += mod;
    cout << ans << '\n';
    return 0;
}