Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
168665 | C班 郑筱橦 | 组合数的高精度算法 | C++ | 解答错误 | 50 | 1 MS | 264 KB | 847 | 2024-08-20 13:00:55 |
#include <iostream> #include <vector> using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll modpow(ll base, ll exp, ll mod) { ll result = 1; base %= mod; while (exp > 0) { if (exp & 1) result = (result * base) % mod; base = (base * base) % mod; exp >>= 1; } return result; } ll inv(ll num, ll mod) { return modpow(num, mod - 2, mod); } ll nCr(ll n, ll r, ll mod) { ll num = 1, den = 1; for (ll i = 1; i <= r; ++i) { num = (num * (n - i + 1)) % mod; den = (den * i) % mod; } return (num * inv(den, mod)) % mod; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ll M, N; cin >> M >> N; ll paths = nCr(M + N - 2, min(M - 1, N - 1), MOD); cout << paths; return 0; }