社区讨论

0pts RE 求助

P3807【模板】卢卡斯定理 / Lucas 定理参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1710u0
此快照首次捕获于
2023/10/22 16:14
2 年前
此快照最后确认于
2023/11/02 15:52
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

int t;
const int maxn = 1e5 + 10;
int n, m, mod;
int fa[maxn];

inline int qp(int a, int b) {
	int ans = 1, B = b;
	a %= mod;
	while (B) {
		if (B & 1) ans = a * ans % mod;
		a = a * a % mod;
		B >>= 1;
	}
	return ans % mod;
}

inline void getfa() {
	fa[0] = 1;
	for (int i = 1; i <= mod; i++) fa[i] = fa[i - 1] * i, fa[i] %= mod;
}

inline int read() {
	int s = 0;
	char c = getchar();
	while (isdigit(c)) s = s * 10 + c - '0', c = getchar();
	return s;
}

inline int C(int n, int m) { return (m > n) ? 0 : fa[n] * qp(fa[m], mod - 2) % mod * qp(fa[n - m], mod - 2) % mod; }

inline int lucas(int n, int m) { return (!m) ? 1 : C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod; }  

signed main() {
	t = read();
	while (t--) {
    	n = read(), m = read(), mod = read(), getfa();
    	cout << lucas(n + m, n) % mod << endl;
	}

	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...