NOIP2011计算系数详解[通俗易懂]

全栈程序员-用户IM • 2022年9月25日下午12:00 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

原题见洛谷（https://www.luogu.org/problem/show?pid=1313）
想看稍微简单点的就是NOIP2016的组合数问题，小飞机~（http://blog.csdn.net/a1351937368/article/details/76907902）
先说一下这道题需要用到：组合数（杨辉三角），乘方
做这道题的感受：题目中说(by+ax)^k，而输入顺序是先a后b搞得我60分emmmm，膜10007记得要开long long有可能会爆int
根据二项式定理，（x+y）^k中x^m*y^（k-m）的系数为C（k，m）
让我们改装一下：（ax+by）^k中x^m*y^（k-m）的系数为C（k，m）*a^m*b^（k-m）
然后这道题就可以乖乖的AC啦~再加点玄学卡常数和优化这道题总时间0ms（其实没必要）
代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

const int maxn=1500;
int c[maxn][maxn];

inline int read(){
    int num;
    char ch;
    while((ch=getchar())<'0' || ch>'9');
    num=ch-'0';
    while((ch=getchar())>='0' && ch<='9'){
        num=num*10+ch-'0';
    }
    return num;
}
inline void out(int x){
    if(x>=10){
        out(x/10);
    }
    putchar(x%10+'0');
}
inline int time(int p,int q){
    if(q==0){
        return 1;
    }
    long long ans=1;
    for(register int i=1;i<=q;++i){
        ans*=p,ans%=10007;
    }
    return ans;
}

int main(){
    int b=read(),a=read(),k=read(),n=read(),m=read();
    long long ans;
    c[0][0]=1;
    for(register int i=1;i<=k;++i){
        c[i][0]=c[i][i]=1;
    }
    for(register int i=1;i<=k;++i){
        for(register int j=1;j<i;++j){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007;
        }
    }
    ans=c[k][m]*(time(a,m)*time(b,n)%10007)%10007;
    out(ans);
    return 0;
}