洛谷P1313 [NOIP2011]计算系数

题目描述

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

输入格式

共一行，包含

输出格式

共1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对

$x^n y^m 的系数为 C[k][n]*a^n*b^m，所以组合数+快速幂即可。$

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 1010
 6 #define mod 10007
 7 
 8 using namespace std;
 9 
10 int a,b,k,n,m;
11 long long c[maxn][maxn];
12 
13 inline int quick_pow(int x,int y)
14 {
15     if(y==1) return x%mod;
16     int t=quick_pow(x,y/2);
17     if(y%2==0) return t%mod*t%mod;
18     else return x%mod*t%mod*t%mod;
19 }
20 
21 int main()
22 {
23     scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
24     c[1][0]=1; c[1][1]=1;
25     for(register int i=2;i<=k;++i)
26     {
27         c[i][0]=c[i][i]=1;
28         for(register int j=1;j<i;++j)
29             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
30     }
31     printf("%d",(quick_pow(a,n)*quick_pow(b,m)*c[k][n])%mod);
32     return 0;
33 }