专栏文章

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

GGoldenSTEVE7
P1313题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqklc5p
此快照首次捕获于
2025/12/04 06:20
3 个月前
此快照最后确认于
2025/12/04 06:20
3 个月前
查看原文

题意

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

分析

本题的求解需要用到一个定理：二项式定理。
(x+y)n=∑i=0nCni×xiyn−i(x+y)^n = \sum^n_{i = 0}C^i_n \times x^iy^{n-i}
该定理的证明不会的可以去百度一下，在这里我就不详细证明了。
我们观察一下原式，发现这不就是二项式定理的样子吗，直接硬拆！
(by+ax)k=∑i=0nCki×(by)i(ax)k−i(by+ax)^k = \sum^n_{i = 0}C^i_k \times (by)^i(ax)^{k-i}
我们要找的 xnymx^ny^m 项即为当上式的 ii 取到了 k−nk-n 时的那一项，具体为 Ckn×(by)k−n(ax)nC^n_k \times (by)^{k-n}(ax)^{n}。化简一下，是 Cknbk−nan×ynxk−nC^n_k b^{k-n} a^n \times y^nx^{k-n}。在这之中 ana^n 与 bmb^m 均需要快速幂进行计算。
那么接下来问题又来了，CknC^n_k 如何计算呢？
这时候我们需要用到组合数的定义式：
Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n-m)!}
但是由于计算中包含了除法，所以我们还需要通过逆元进行计算。
下面是科普时间（学习过逆元的大佬可以直接跳过）：
我们看下面一个式子：
a×a−1=1a\times a^{-1} = 1
是不是很有道理。
那么我们在取模的时候，也是可以这么干的。
a×a−1≡1(modp)a\times a^{-1} \equiv 1 \pmod p
这其中 a−1a^{-1} 被称作 “aa 在模 pp 意义下的逆元”。
那我们可以发现，两个正整数 n,mn,m，一定 nm−1≡n×(1÷m)≡nm(modp)nm^{-1} \equiv n \times (1 \div m) \equiv \displaystyle\frac{n}{m} \pmod p
那么我们就可以回到上面的那个式子啦！
所以
Cnm≡n!m!(n−m)!≡n!×[m!(n−m)!]−1(modp)C_n^m \equiv \frac{n!}{m!(n-m)!} \equiv n! \times [m!(n-m)!]^{-1} \pmod p
那么问题又又来了，咋求逆元啊？
这就不得不再提到一个定理了——费马小定理：
如果 pp 是一个质数，而整数 aa 与 pp 互质，则有 ap−1≡1(modp)a^{p-1}\equiv 1 \pmod p
我们的目标是通过这个定理去求 aa 的逆元。
接下来不要眨眼，由于 aa 与 pp 互质，所以我们可以将同余式子的两边大胆同时除以 aa 就可以得到：
ap−2≡1÷a≡a−1(modp)a^{p-2}\equiv 1\div a\equiv a^{-1} \pmod p
吔，这右边不就是 aa 在模 pp 意义下的逆元吗？
所以我们就得到了结论：aa 在模 pp 意义下的逆元等于 aa 的 p−2p-2 次方。
好的以上是对于逆元的科普。
回到原题，那么这个可爱（可恶）的 CknC_k^n 就可以求出来了。
最后将其与 an×bma^n\times b^m 相乘输出即可。

代码

CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...