-
原题链接:B3717 组合数问题。
-
难度:
Easy
组合数学的模板题。
排除做法:
- \(n,m\le5\times10^6\),显然不能使用杨辉三角递推。
- 模数为 \(998,244,353\),无法使用 \(\text{Lucas}\) 定理。
正解
考虑直接使用组合数的计算式:
\[{n\choose m}=\dfrac{n!}{m!(n-m)!} \]其中 \(n!\) 可以直接线性递推。
对于 \(\dfrac{1}{i!}\) 可以先线性递推出每个数的逆元(详见 乘法逆元),然后从前往后像 \(n!\) 那样递推即可,详见代码。
代码
#include <bits/stdc++.h>
using lint = long long;
const int MAXN = 5e6 + 10;
const int MOD = 998244353;
int T, N;
lint n, m, ans, inv[MAXN], fact[MAXN], inv_fact[MAXN];
void init() {
inv[0] = inv[1] = 1;
for (int i = 2; i <= N; ++i) // 线性递推 1~N 的逆元
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= N; ++i) {
fact[i] = fact[i - 1] * i % MOD;
inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD;
}
}
lint C(int n, int m) { // 根据公式计算
if (m > n) return 0;
if (m == n) return 1;
return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}
int main() {
std::cin.tie(0)->sync_with_stdio(0); // 加速读入
std::cin >> T >> N, init();
while (T--) {
std::cin >> n >> m;
ans ^= C(n, m);
}
std::cout << ans << std::endl;
return 0;
}
标签:std,return,LGB3717,int,题解,inv,MAXN,fact
From: https://www.cnblogs.com/oier-wst/p/18434356/luogu-B3717-solution