lgB3717 计算组合数

给出T次询问，每次给出n和m，求C(n,m)对998244353取模的结果。为了避免输出太多内容，只需要输出所有查询结果的异或和。
1<=T<=5E6; 0<=m<=n<=5E6

先O(n)预处理出所有数的阶乘及其对应的乘法逆元，然后O(1)处理每次询问。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

const int MOD = 998244353;
const int Z = 5000005;
int T, N, fac[Z], ifac[Z];
int comb(int n, int m) {
    return fac[n] * ifac[m] % MOD * ifac[n-m] % MOD;
}
int power(int a, int b) {
    int r = 1;
    for (int t = a; b; b /= 2) {
        if (b & 1) r = r * t % MOD;
        t = t * t % MOD;
    }
    return r % MOD;
}
void solve() {
    cin >> T >> N;
    fac[0] = 1;
    rep(i,1,N) fac[i] = fac[i-1] * i % MOD;
    ifac[N] = power(fac[N], MOD-2);
    per(i,0,N-1) ifac[i] = ifac[i+1] * (i+1) % MOD;
    int ans = 0;
    while (T--) {
        int n, m;
        cin >> n >> m;
        ans ^= comb(n, m);
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}