计算系数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1015 字

求^k展开后x^n·y^m项的系数，对100

一本通
例

正文

/*
原题：T1648「一本通 6.6 例 1」计算系数
题意：求 (a·x+b·y)^k 展开后 x^n·y^m 项的系数，对 10007 取模。
思路：由二项式定理，该项系数为 C(k,n)·a^n·b^m（必有 n+m=k）。
C(k,n) 用杨辉三角递推在模 10007 下算出，幂用快速幂即可。
复杂度：时间 O(k^2+log k)，空间 O(k^2)
易错点：1) 取的是 C(k,n) 而不是 C(k,m)，两者相等，别写成 C(k,n+m)；
2) a、b 先对 10007 取模再乘，防止溢出；
3) 组合数递推时每行只更新到 i，注意倒序或用二维数组。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=10007;
long long qpow(long long a,long long n){
    long long r=1;
    a%=MOD;
    while(n>0){
        if(n&1){
            r=r*a%MOD;
        }
        a=a*a%MOD;
        n>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long a,b;
    int k,n,m;
    cin>>a>>b>>k>>n>>m;
    vector<vector<long long>> c(k+1,vector<long long>(k+1,0));
    c[0][0]=1;
    for(int i=1;i<=k;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
        }
    }
    long long ans=c[k][n];
    ans=ans*qpow(a,n)%MOD;
    ans=ans*qpow(b,m)%MOD;
    cout<<ans<<"\n";
    return 0;
}

计算系数

正文

一本通·提高篇的其它内容