本文主要是介绍上海计算机学会 2023年9月月赛 乙组T4 组合数（组合数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第四题：T4组合数
标签：组合数学
题意：求组合数 C n m C_n^m Cnm，即从 n n n个不同的数字中取出 m m m个数字的方案数，结果对 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007取模
（ 1 ≤ m ≤ n ≤ 1 0 9 ， 1 ≤ m ≤ 1 0 6 1≤m≤n≤10^9，1≤m≤10^6 1≤m≤n≤109，1≤m≤106）
题解：直接通过通项公式 C n m = n ! m ! ( n − m ) ! C_n^m=\frac {n!}{m!(n-m)!} Cnm=m!(n−m)!n!，值得注意的是要进行取模，所以得用到逆元 i n v inv inv。
费马小定理： a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1(mod \ p) ap−1≡1(mod p)，两边同时除以 a a a， a p − 2 ≡ i n v ( a ) ( m o d p ) a^{p-2}≡inv(a)(mod\ p) ap−2≡inv(a)(mod p)，即 i n v ( a ) = a p − 2 ( m o d p ) inv(a)=a^{p-2}(mod \ p) inv(a)=ap−2(mod p)，得到 a p − 2 a^{p-2} ap−2这部分可以通过快速幂去得到。
代码：
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll p = 1e9 + 7;ll fast_power(ll a, ll b) {ll ans = 1;a %= p;while (b) {if (b & 1) ans = (ans * a) % p;a = (a * a) % p;b >>= 1;}return ans;
}ll C(ll a, ll b) {if (b > a) return 0;if (a == b) return 1;ll ans1 = 1, ans2 = 1;for (ll i = 1; i <= b; i++) {ans1 = ans1 * (a - i + 1) % p;ans2 = ans2 * i % p;}return ans1 * fast_power(ans2, p - 2) % p;
}int main() {ll n, m;cin >> n >> m;cout << C(n, m);return 0;
}
这篇关于上海计算机学会 2023年9月月赛 乙组T4 组合数（组合数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
