为什么 Lucas 里面判 n == 0 也能过?
查看原帖
为什么 Lucas 里面判 n == 0 也能过?
902351
Little_x_starTYJ楼主2024/10/21 21:58

是数据水还是性质?

#include <bits/stdc++.h>
using namespace std;
#define int long long
int fac[100010];
inline int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
inline int C(int n, int m, int mod) {
	if (n < m)
		return 0;
	return fac[n] * qmi(fac[m] * fac[n - m], mod - 2, mod) % mod;
}
inline int Lucas(int n, int m, int mod) {
	if (n == 0)
		return 1;
	return C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod) % mod;
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, m, p;
		cin >> n >> m >> p;
		fac[0] = 1;
		for (int i = 1; i <= p; i++) fac[i] = fac[i - 1] * i % p;
		cout << Lucas(n + m, n, p) << "\n";
	}
}
2024/10/21 21:58
加载中...