B3717 题解
sto_5k_orz
·
·
题解
C_n^m={\dfrac{n!}{m!\times(n-m)!}}
那么可以理解为 n!\times (m!)^{-1}\times (n-m!)^{-1}。
接下来是预处理阶乘的逆元 $(x!)^{-1}$。
显然可得 $(x!)^{-1}=({(x-1)!)^{-1}\times x^{-1}}$。
那么先线性递推 $x^{-1}$，再线性递推 $(x!)^{-1}$ 即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define pc putchar
const int N = 5000010;
int inv[N], jc[N], Jc[N];
const int p = 998244353;
void init(int n, int p) {
inv[1] = 1, jc[0] = 1, Jc[0] = 1;
for(int i = 2; i <= n; i++) inv[i] = 1LL * (p - p / i) * inv[p % i] % p; // 线性求逆元
for(int i = 1; i <= n; i++) jc[i] = 1LL * jc[i - 1] * inv[i] % p, Jc[i] = 1LL * Jc[i - 1] * i % p; // 线性求阶乘逆元
}
signed main() {
ios::sync_with_stdio(0);
int ans = 0, t, maxn; cin >> t >> maxn; init(maxn, p);
while(t--) {
int n, m; cin >> n >> m;
int a = 1LL * Jc[n] * jc[m] % p * jc[n - m] % p;
ans ^= a;
}
cout << ans << endl;
return 0;
}
```