洛谷 P1313 计算系数（算法竞赛进阶指南，快速幂，组合数，乘法逆元）

算法竞赛进阶指南，171 页，快速幂，组合数，乘法逆元

本题要点：
1、通过二项式定理，求出 x^n * y^m 项的系数是 C[n][k] * a^n * b^m.

2、幂 的计算 a^n 直接使用快速幂计算， 假设得到结果是 ans;
3、组合数 C[n][k] 的计算：
先计算 k! , 再计算阶乘 n! * (k - n)! 模p的逆元。 p是素数，那么
欧拉定理有： t^(p - 1)=1(mod p), 也就是t 模p的逆元是 t^(p - 2)。
因此 n! * (k - n)! 模p的逆元 是 (n! * (k - n)!) ^ (p - 2)。
假设得到结果是 t1， 最后将 ans * t1 再模 p即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const long long mod = 10007;
long long a, b, k, n, m;long long quick_pow(long long x, long long y)
{
    long long ans = 1;while(y > 0){
    if(y & 1){
    ans = (ans * x) % mod;}y >>= 1;x = (x * x) % mod;}return ans;
}void solve()
{
    // c[k][n] * a^n * b^mlong long ans = 1;ans = (ans * quick_pow(a, n)) % mod;ans = (ans * quick_pow(b, m)) % mod;long long t1 = 1, t2 = 1;for(int i = 1; i <= k; ++i){
    t1 = (t1 * i) % mod;}for(int i = 1; i <= n; ++i){
    t2 = (t2 * i) % mod;	}for(int i = 1; i <= k - n; ++i){
    t2 = (t2 * i) % mod;	}
// printf("ans = %lld\n", ans);t1 = (t1 * quick_pow(t2, mod - 2)) % mod;
// printf("t1 = %lld\n", t1);ans = (ans * t1) % mod;printf("%lld\n", ans);
}int main()
{
    scanf("%lld%lld%lld%lld%lld", &a, &b, &k, &n, &m);solve();return 0;
}/* 1 1 3 1 2 *//* 3 */