P3807[模板]卢卡斯定理

本文主要是介绍P3807[模板]卢卡斯定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

需要特判n < m的时候,return 0

#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
using namespace std;
const int N = 1e6 + 5;
int f[N], g[N],mod;
int qpow(int a, int b) {int res = 1;while (b) {if (b & 1) res = a * res % mod;a  = a * a % mod, b >>= 1;}return res;
}
void init(int n,int m) {memset(f, 0, sizeof f);memset(g, 0, sizeof g);f[0] = g[0] = 1;for (int i = 1; i <= n + m; ++i) {f[i] = f[i - 1] * i % mod;g[i] = g[i - 1] * qpow(i, mod - 2) % mod;}
}
int getc(int n, int m) {if (n < m) return 0;return f[n] * g[m] % mod * g[n - m] % mod;
}
int Lucas(int n,int m) {if (m == 0) return 1;return Lucas(n / mod, m / mod) * getc(n % mod, m % mod) % mod;
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t,n,m,ans = 0; cin >> t;while (t--) {cin >> n >> m >> mod;init(n, m);cout << Lucas(n + m, m) % mod << endl;}return 0;
}

这篇关于P3807[模板]卢卡斯定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---