「NOIP2011」 计算系数 - 组合数

题目描述

给定一个多项式$(ax+by{)}^k$,请求出多项式展开后$x^n{y}^m$项的系数.

输入格式

共一行,包含5个整数,分别为$a,b,k,n,m,$每两个整数之间用一个空格隔开.

输出格式

出共1行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007取模后的结果.

样例输入

1 1 3 1 2

样例输出

3

数据规模与约定

对于30%的数据,有$0\le k\le 10$; 对于50%的数据,有$a=1,b=1$ ; 对于100%的数据,有$0\le k\le 1000,0\le n,m\le k,$且$n+m=k,0\le a,b\le 1000000$.

分析

看到形如$(x+y{)}^n$的形式的题,马上想到杨辉三角.由杨辉三角,可以很轻易地得到$x^n{y}^m$前面的常数,同时,我们也可以知道,$a,b$的指数是和$x,y$是一样的,又因为$k$很大,不难想到快速幂的算法.至于快速幂,网上的文章很多,这里就不过多赘述.

代码

#include <iostream> #include <cmath> #include <cstdio> using namespace std; long long s[1010][1010]; int a,b,k,n,m; long long ans; long long fast_pow(int x,int y,int mod) {//快速幂 long long base=x,t=1;//注意!!10006*10006可能会爆int for (;y;base=base*base%mod,y>>=1) if (y&1) t=t*base%mod; return t; } int main() { scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); s[1][1]=1;//计算杨辉三角 for (int i = 2;i <= k+1;i++) { for (int j = 1;j <= i;j++) { s[i][j]=(s[i-1][j]+s[i-1][j-1])%10007; } } ans=(s[k+1][k-n+1]*fast_pow(a,n,10007)*fast_pow(b,m,10007))%10007; printf("%lld",ans); return 0; }