社区讨论
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 条回复,欢迎继续交流。
正在加载回复...