COJ 0138 NOIP201108计算系数

NOIP201108计算系数

难度级别：A；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

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

输入

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

输出

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

输入示例

1 1 3 1 2

输出示例

其他说明

【数据范围】0≤k≤1,000，0≤n, m≤k，且n+m=k，0≤a，b≤1,000,000。

题解：先胡搞出答案是：C(n,n+m) * a^n * b^m

然后呢，指数部分用快速幂，C用逆元搞。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int mod=10007;
11 void exgcd(int a,int b,int&x,int&y){
12     if(!b){x=1;y=0;return;}exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return;
13 }
14 int pow(int x,int y){
15     int ans=1;x%=mod;for(int i=y;i;i>>=1,x=x*x%mod)if(i&1)ans=ans*x%mod;return ans;
16 }
17 int ine(int t){
18     int x,y;exgcd(t,mod,x,y);x%=mod;if(x<=0)x+=mod;return x;
19 }
20 int C(int n,int m){
21     int s1=1,s2=1;if(m>n-m)m=n-m;
22     for(int i=1;i<=m;i++){
23         s1=s1*(n-i+1)%mod;
24         s2=s2*i%mod;
25     }return s1*ine(s2)%mod;
26 }
27 inline int read(){
28     int x=0,sig=1;char ch=getchar();
29     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
30     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
31     return x*=sig;
32 }
33 inline void write(int x){
34     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
35     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
36     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
37 }
38 int a,b,k,n,m;
39 void init(){
40     a=read();b=read();k=read();n=read();m=read();
41     write(C(k,n)%mod*pow(a,n)%mod*pow(b,m)%mod);
42     return;
43 }
44 void work(){
45     return;
46 }
47 void print(){
48     return;
49 }
50 int main(){
51     init();work();print();return 0;
52 }