【NC16596】计算系数

本文主要是介绍【NC16596】计算系数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

计算系数

组合数，快速幂

思路

这是一道数学题，由之前的数学知识可以知道，题目要我们算一个数：$(C_k^m{a}^n{b}^m)\mathrm{mod}10007$

题意很明显，没有弯弯绕，就是要求这个数！可以知道，这个数由一个组合数和两个幂相乘，幂运算很好求，使用快速幂即可，组合数的求法有很多，这里记录卢卡斯定理（见字符串）

代码

#include <stdio.h>#define MOD 10007typedef long long LL;// 老朋友：快速幂
int quick_pow(int a, int b, int p) {int res = 1;while (b) {if (b & 1) {res = (LL)res * a % p;}a = (LL)a * a % p;b >>= 1;}return res;
}// 求 a 在模 p 条件下的逆元，要求 a 与 p 互质
int inv(int a, int p) { return quick_pow(a, p - 2, p); }// 卢卡斯定理求组合数 C(n,m) % p 的值
int lucas(int n, int m, int p) {if (!m) return 1;int ni = n % p, mi = m % p;if (ni < mi) return 0;int res = 1;for (int i = 0; i < mi; i++) {res = (LL)res * (ni - i) % p * inv(i + 1, p) % p;}return res * lucas(n / p, m / p, p) % p;
}int main(void) {int a = 0, b = 0, k = 0, n = 0, m = 0;scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);printf("%d\n", (lucas(k, m, MOD) * quick_pow(a, n, MOD)) % MOD *quick_pow(b, m, MOD) % MOD);return 0;
}

这篇关于【NC16596】计算系数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---