题解：P1313 [NOIP2011 提高组] 计算系数

· · 题解

题意

求多项式 (by+ax)^k 展开后 x^ny^m 项的系数。

分析

本题的求解需要用到一个定理：二项式定理。

(x+y)^n = \sum^n_{i = 0}C^i_n \times x^iy^{n-i}

该定理的证明不会的可以去百度一下，在这里我就不详细证明了。

我们观察一下原式，发现这不就是二项式定理的样子吗，直接硬拆！

(by+ax)^k = \sum^n_{i = 0}C^i_k \times (by)^i(ax)^{k-i}

我们要找的 x^ny^m 项即为当上式的 i 取到了 k-n 时的那一项，具体为 C^n_k \times (by)^{k-n}(ax)^{n}。化简一下，是 C^n_k b^{k-n} a^n \times y^nx^{k-n}。在这之中 a^n 与 b^m 均需要快速幂进行计算。

那么接下来问题又来了，C^n_k 如何计算呢？

这时候我们需要用到组合数的定义式：

C_n^m = \frac{n!}{m!(n-m)!}

但是由于计算中包含了除法，所以我们还需要通过逆元进行计算。

下面是科普时间（学习过逆元的大佬可以直接跳过）：

我们看下面一个式子：

a\times a^{-1} = 1

是不是很有道理。

那么我们在取模的时候，也是可以这么干的。

a\times a^{-1} \equiv 1 \pmod p

这其中 a^{-1} 被称作 “a 在模 p 意义下的逆元”。

那我们可以发现，两个正整数 n,m，一定 nm^{-1} \equiv n \times (1 \div m) \equiv \displaystyle\frac{n}{m} \pmod p

那么我们就可以回到上面的那个式子啦！

所以

C_n^m \equiv \frac{n!}{m!(n-m)!} \equiv n! \times [m!(n-m)!]^{-1} \pmod p

那么问题又又来了，咋求逆元啊？

这就不得不再提到一个定理了——费马小定理：

如果 p 是一个质数，而整数 a 与 p 互质，则有 a^{p-1}\equiv 1 \pmod p

我们的目标是通过这个定理去求 a 的逆元。

接下来不要眨眼，由于 a 与 p 互质，所以我们可以将同余式子的两边大胆同时除以 a 就可以得到：

a^{p-2}\equiv 1\div a\equiv a^{-1} \pmod p

吔，这右边不就是 a 在模 p 意义下的逆元吗？

所以我们就得到了结论：a 在模 p 意义下的逆元等于 a 的 p-2 次方。

好的以上是对于逆元的科普。

回到原题，那么这个可爱（可恶）的 C_k^n 就可以求出来了。

最后将其与 a^n\times b^m 相乘输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int p = 10007;
ll fpow(ll a, ll b) {
    ll ret = 1;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret*a%p; 
        a = a*a%p;
    }
    return ret;
}//快速幂
ll inv(ll x) {return fpow(x,10005);}//求逆元
int main() {
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    ll N = 1, KN = 1, K = 1;
    ll ans = fpow(a, n) * fpow(b, m); ans %= p;
    if(n > m) n = m;
    for(int i = 1; i <= n; i++) N *= i, N %= p;
    for(int i = 1; i <= k; i++) K *= i, K %= p;
    for(int i = 1; i <= k-n; i++) KN *= i, KN %= p;
    //分别求出n!,k!,(k-n)!
    ans = ans * K * inv(N*KN%p) % p;
    cout << ans;
    return 0;
}