B3717题解2

sto_5k_orz · 2023-03-23 16:56:13 · 题解

上一篇题解

考虑直接根据费马小定理求出 (n!)^{-1}。

然后根据 (i!)^{-1}=(i+1)!^{-1}\times (i+1) 反推回去，这样更加巧妙，但理论上复杂度一样。

显然时效更好，因为不需要求逆元了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 5, p = 998244353;
ll f[N], inv[N], t, maxn;
ll Pow(ll a, int b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> maxn; f[0] = 1;
    for(int i = 1; i <= maxn; i++) f[i] = f[i - 1] * i % p;
    inv[maxn] = Pow(f[maxn], p - 2);
    for(int i = maxn - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % p; // 反推阶乘逆元
    int ans = 0;
    while(t--) {
        int n, m; cin >> n >> m;
        ll tmp = f[n] * inv[m] % p * inv[n - m] % p;
        ans ^= tmp;
    }
    cout << ans;
    return 0;
}

在 C++20 O2 的环境下：

本题解代码 1.11s 通过。

上一篇 1.19s。

80ms 差距不大。