牛客OI周赛4-提高组 B 最后的晚餐(dinner)

时间：2022-10-06 20:47:06

最后的晚餐(dinner)

思路:

容斥

求 ∑(-1)^i * C(n, i) * 2^i * (2n-i-1)!

这道题卡常数

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const LL MOD = 1e9 + ;

const int N = 3e7 + ;

int f[N], inv[N];

LL q_pow(LL n, LL k) {

    LL ans = ;

    while(k) {

        if(k&) ans = (ans * n) % MOD;

        n = (n * n) % MOD;

        k >>= ;

    }

    return ans;

}

int main() {

    int n;

    scanf("%d", &n);

    if(n == ) return *puts("");

    LL ans = ;

    int fac = , pw = q_pow(, n), c = ;

    f[] = ;

    for (int i = ; i <= n; i++) f[i] = (1LL * f[i-] * i) % MOD;

    inv[n] = q_pow(f[n], MOD-) % MOD;

    for (int i = n-; i >= ; i--) inv[i] = (1LL * inv[i+]*(i+)) % MOD;

    fac = f[n-];

    for (int i = n; i >= ; i--) {

        (ans += ((i%) ? - : ) * 1LL * inv[i] % MOD * inv[n-i] % MOD * pw % MOD * fac) %= MOD;

        fac = (1LL * fac * (*n - i)) % MOD;

        pw = (1LL * pw * inv[]) % MOD;

    }

    ans = (ans + MOD) % MOD;

    ans = ans * f[n] % MOD;

    printf("%lld\n", ans);

    return ;

}

相关文章