杨辉三角加快速幂秒过 (o ° ω ° O )
记得用long long！！！被这个卡了五次

#include<iostream>
using namespace std;
long long a,b,k,n,m,ans;
long long yh[1005][1005];
int quickpow(int a,int b,int c)
{
    int ans=1;
    a=a%c;
    while(b!=0)
    {
        if(b&1)
        ans=(ans*a)%c;
        a=(a*a)%c;
        b=b>>1;
    }
    return ans;
}
int main()
{
    cin>>a>>b>>k>>n>>m;
    for(int i=0;i<=1000;++i)
    {
        yh[i][0]=1;
        for(int j=1;j<=i;++j)
        yh[i][j]=(yh[i-1][j]+yh[i-1][j-1])%10007;
    }
    ans=(quickpow(a,n,10007)*quickpow(b,m,10007)*yh[k][m])%10007;
    cout<<ans;
    return 0;
}

根据二项式定理x^n*y^m的系数可表示为a^n*b^m*C(k,m)。
所以本题可以用杨辉三角递推c[i][j]=c[i-1][j]+c[i-1][j-1].

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define LL long long 
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int MOD=10007;
LL a,b,k,n,m,C[1005][1005];

void get(int x,int y){
    C[1][0]=C[1][1]=1;
    for(int i=2;i<=x;++i){
        C[i][0]=1;
        for(int j=1;j<=y;++j)
            C[i][j]=C[i-1][j-1]+C[i-1][j],C[i][j]%=MOD;
    }
}
LL ks(LL x,int y){
    LL s=1;
    while(y){
        if(y&1)s*=x,s%=MOD;
        y>>=1;
        x*=x;
        x%=MOD;
    }
    return s;
}
int main(){
    read(a),read(b),read(k),read(n),read(m);
    get(k,m);
    printf("%lld",((C[k][m]*ks(a,n)%MOD)*ks(b,m))%MOD);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

long long f[1005][1005];
int main()
{
    int a,b,k,n,m; cin>>a>>b>>k>>n>>m;
    f[0][0]=1;
    for (int i=0; i<=n; i++){
        for (int j=0; j<=m; j++){
            if (i==0 && j==0)
                continue;
            f[i][j]=0;
            if (i>0)
                f[i][j]=(f[i][j]+f[i-1][j]*a)%10007;
            if (j>0)
                f[i][j]=(f[i][j]+f[i][j-1]*b)%10007;
        }
    }
    cout<<f[n][m];
    return 0;
}

每人用逆元法吗?
那我来一个(复杂度nlogn)
(虽然正解是用杨辉,但这个代码可以过k=100000的数据!(不过要把里面的数全都换成long long))

//求a^n*b^m*C(k,n)
//快速幂求前两个,组合数用扩欧求逆元进行除法计算
//组合数有更好的求法就是杨辉三角形打表(但是复杂度较高,我这里给个更好的)
//总复杂度O(nlogn) 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define mod 10007
using namespace std;
int n,m,k,e,f;
typedef long long ll;
int pow(int a,int x){//快速幂(注意要开long long!!!) 
    if(a==0) return 0;
    ll w=a,res=1,i=x;
    while(i){
        if(i&1) res=(res*w)%mod;
        w=(w*w)%mod;
        i>>=1;
    }
    return (int)res;
}
int exgcd(int a,int b,int &x,int &y){//扩欧 
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int res=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return res;
}
int getC(int a,int b){//下标b,上标a ,求组合数 
    int i,res=1,x,y;
    if(a>b/2) a=b-a;
    for(i=b;i>b-a;i--){
        res=(res*i)%mod;
    }
    for(i=2;i<=a;i++){
        exgcd(i,mod,x,y);
        if(x<0) x=(x%mod)+mod;
        res=(res*x)%mod;
    }
    return res;
}
int main(){
    int ans=1;
    cin>>e>>f>>k>>n>>m;
    ans=(ans*pow(e,n))%mod;
    ans=(ans*pow(f,m))%mod;
    ans=(ans*getC(n,k))%mod;
    cout<<ans;
    return 0;
}

杨辉三角预处理
O(k^2+lgn)

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int y[1001][1001];
int a,b,k,n,m;
void yhsj()
{
    for(int i=0;i<=1000;i++)
    {
        y[i][0]=1;
        y[i][i]=1;
    }
    for(int i=2;i<=1000;i++)
    {
        for(int j=1;j<i;j++)
        {
            y[i][j]=(y[i-1][j-1]+y[i-1][j])%10007;
        }
    }
    return;
}
long long zym(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b%2==1)
        {
            ans=(ans*a)%10007;
        }
        a=(a*a)%10007;
        b>>=1;
    }
    return ans%10007;
}
int main()
{
    yhsj();
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a%=10007;
    b%=10007;
    printf("%d",(y[k][m]*zym(a,n)*zym(b,m))%10007);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int key=10007,oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int a,b,t,n,m;
int c[1000+1][1000+1];

int main()
{
    while (~scanf("%d%d%d%d%d",&a,&b,&t,&n,&m))
    {
        for (int i=0;i<=t;i++)
            c[i][0]=c[i][i]=1;
        for (int i=2;i<=t;i++)
            for (int j=1;j<i;j++)
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%key;
        a%=key,b%=key;
        int temp_1=1,temp_2=1;
        for (int i=1;i<=n;i++)
            temp_1=(temp_1*a)%key;
        for (int i=1;i<=m;i++)
            temp_2=(temp_2*b)%key;
        int ans=(((c[t][n]*temp_1)%key)*temp_2)%key;
        printf("%d\n",ans);
    }
}

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MOD=10007;
int n,m,a,b,k,ans=1;
int yh[1003][1010]={0};

void build_yh()
{
yh[0][0]=yh[1][0]=yh[1][1]=1;
for(int i=2;i<=k;i++)
{
yh[i][0]=yh[i][i]=1;
for(int j=1;j<i;j++)
yh[i][j]=(yh[i-1][j-1]+yh[i-1][j])%MOD;
}
}
int main()
{
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
a%=MOD;b%=MOD;
build_yh();
for(int i=0;i<n;i++)
ans=ans*a%MOD;
for(int i=0;i<m;i++)
ans=ans*b%MOD;
ans=ans*yh[k][n]%MOD;

cout<<ans;
return 0;
}

这道题用杨辉三角计算C（k，m）!!!

#include<iostream>
#include<cstdio>
using namespace std;
int a,b,k,n,m;
int f[1005][1005]={0};
int pow(int p,int time){
int i,re=1;
p=p%10007;
for(i=1;i<=time;i++){
re=(re*p)%10007;
}
return re;
}
int main(){
//freopen("factor9.in","r",stdin);
int i,j,ans=1;
cin>>a>>b>>k>>n>>m;
int r1,r2,r3;
r1=pow(a,n);
r2=pow(b,m);
f[1][1]=1;f[1][2]=1;
for(i=2;i<=k;i++){
for(j=1;j<=i+1;j++){
f[i][j]=(f[i-1][j-1]+f[i-1][j])%10007;
}
}
r3=f[k][m+1];
ans=(((r1*r2)%10007)*r3)%10007;
cout<<ans;
return 0;
}


#include <cstdio>
using namespace std;

int pascal[1002][1002];

int pwr(int base, int exponent)
{
    int sqr[10];
    sqr[0] = base;
    for (int i = 1; i < 10; i++) {
        sqr[i] = sqr[i - 1] * sqr[i - 1];
        sqr[i] %= 10007;
    }
    int ans = 1;
    for (int i = 0; i < 10; i++) {
        if (exponent & (1 << i)) {
            ans *= sqr[i];
            ans %= 10007;
        }
    }
    return ans;
}

int main()
{
    int a, b, k, n, m;
    scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
    pascal[1][1] = 1;
    for (int i = 2; i <= 1001; i++) {
        for (int j = 1; j <= 1001; j++) {
            pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1]) % 10007;
        }
    }
    printf("%d", (((pwr(a%10007, n) * pwr(b%10007, m)) % 10007) * pascal[k+1][n+1]) % 10007);
    return 0;
}

miao...

#include <iostream>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
long long a, b, k, n, m;
long long PA[2000], PB[2000], C[2000][2000];
long long pa(long long x){
    if (PA[x] != 0){
        return PA[x];
    }
    if (x == 0){
        return PA[x] = 1;
    }
    return PA[x] = (pa(x - 1) * a) % 10007;
}
long long pb(long long x){
    if (PB[x] != 0){
        return PB[x];
    }
    if (x == 0){
        return PB[x] = 1;
    }
    return PB[x] = (pb(x - 1) * b) % 10007;
}
long long c(long long x, long long y){
    if (x < y || y < 0){
        return 0;
    }
    if (y == 0){
        return 1;
    }
    if (x == y){
        return 1;
    }
    if (C[x][y] != 0){
        return C[x][y];
    }
    return C[x][y] = (c(x - 1, y - 1) + c(x - 1, y)) % 10007;
}
int main(){
    cin >> a >> b >> k >> n >> m;
    cout << (c(k, m) * pa(n) * pb(m)) % 10007 << endl;
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#define Q 10007

int main(){
long long q=1,a,b,f1[1200]={0},f2[1200]={0};
int k,n,m;
std::cin>>a>>b>>k>>n>>m;
f1[0]=1,f1[1]=1;
for(int i=2;i<=k;i++){
memcpy(f2,f1,sizeof(f1));
f1[0]=f2[0];
for(int j=1;j<=i;j++)
f1[j]=(f2[j-1]+f2[j])%Q;
}
q=f1[n];
for(int i=1;i<=n;i++)
q=(q*a)%Q;
for(int i=1;i<=m;i++)
q=(q*b)%Q;

std::cout<<q;
return 0;
}

要注意维护不要越界；

想公式花了10分钟 敲高精度花了40分钟
最后发现要MOD10007 发现不用高精度.....
公式：i从1到k循环,j从1到k-1，每一次：
result[j+1]+=a x q[j];
result[j]+=b x q[j];
q为上一步的结果 result为这一步的结果
q[p]=m 表示(x^p) * (y^j-p)项的系数=m
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#define M 10007

long long q[1010]={0};
long long temp[1010]={0};

int main(){
int k,n,m;
long long a,b;
std::cin>>a>>b>>k>>n>>m;
q[0]=b;
q[1]=a;
for(int i=2;i<=k;i++){
memset(temp,0,sizeof(temp));
for(int j=0;j<=k-1;j++){
temp[j+1]+=a*q[j];
temp[j]+=b*q[j];
}
for(int j=0;j<=k;j++)
temp[j]%=M;
memcpy(q,temp,sizeof(q));
}
std::cout<<q[n];
return 0;
}

这题纯粹考高中数学
```c++
#include<iostream>
#include<cstdio>
using namespace std;

const int MOD = 10007;
const int maxk = 1000 + 10;

int a, b, k, n, m;
int C[maxk][maxk];

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> a >> b >> k >> n >> m;
int ans = 1;
a = a % MOD; b = b % MOD;
for (int i = 0; i < n; i++)
ans = ans * a % MOD;
for (int i = 0; i < m; i++)
ans = ans * b % MOD;

for (int i = 0; i <= k; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}

ans = ans * C[k][n] % MOD;
cout << ans << "\n";
return 0;
}
```

评测状态 Accepted
题目 P1739 计算系数
递交时间 2016-07-16 08:49:21
代码语言 C++
评测机 ShadowShore
消耗时间 15 ms
消耗内存 556 KiB
评测时间 2016-07-16 08:49:22
评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:54:48: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n",C(k,n)%P*qpow(a,n)%P*qpow(b,m)%P);
^

测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 552 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10

Accepted, time = 15 ms, mem = 556 KiB, score = 100
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#define P 10007
#define N 50005
#define ll long long
#define INF 1000000000
using namespace std;
int a,b,k,n,m;
void exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1;y=0;}
else{exgcd(b,a%b,y,x);y-=x*(a/b);}
}
long long qpow(long long x,long long y)
{
int sum=1;
while(y>0)
{
if(y&1)sum=sum*x%P;
x=x*x%P;
y>>=1;
}
return sum;
}
int ine(int T)
{
int x,y;
exgcd(T,P,x,y);
x%=P;
while(x<=0)x+=P;
return x;
}
int C(int n,int m)
{
int s1=1,s2=1;
if(m>n-m)m=n-m;
for(int i=1;i<=m;i++)
{
s1=s1*(n-i+1)%P;
s2=s2*i%P;
}
return s1*ine(s2)%P;
}
int main()
{
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
printf("%d\n",C(k,n)%P*qpow(a,n)%P*qpow(b,m)%P);
return 0;
}

二项式展开后发现就是求C(k,m)×(a^n)×(b^m)，递推时间长了点但是能过。
~~~
#include <cstdio>
int a,b,n,m,ans,c[1005];
int C(int u,int v){
if(v>u-v) v=u-v;
for(int i=0;i<=v;i++) c[i]=1;
for(int i=1;i<=u-v;i++)
for(int j=1;j<=v;j++)
c[j]=(c[j]+c[j-1])%10007;
return c[v];
}
int P(int u,int v){//power
int x=1;
for(int i=1;i<=v;i++)
x=(x*(u%10007))%10007;
return x;
}
int main(){
scanf("%d%d%*d%d%d",&a,&b,&n,&m);
ans=((C(n+m,m)*P(a,n))%10007*P(b,m))%10007;
printf("%d\n",ans);
return 0;
}

评测状态 Wrong Answer
题目 P1739 计算系数
递交时间 2015-11-07 22:35:48
代码语言 C
评测机 VijosEx
消耗时间 60 ms
消耗内存 4176 KiB
评测时间 2015-11-07 22:35:49
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 4168 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4176 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4168 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 4168 KiB, score = 10
测试数据 #4: WrongAnswer, time = 0 ms, mem = 4172 KiB, score = 0
测试数据 #5: WrongAnswer, time = 15 ms, mem = 4176 KiB, score = 0
测试数据 #6: WrongAnswer, time = 0 ms, mem = 4168 KiB, score = 0
测试数据 #7: Accepted, time = 15 ms, mem = 4168 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 4168 KiB, score = 10
测试数据 #9: WrongAnswer, time = 0 ms, mem = 4168 KiB, score = 0
WrongAnswer, time = 60 ms, mem = 4176 KiB, score = 60
代码
#include<stdio.h>
#define MAX 1001
int pangle[MAX][MAX+1];
int power(int x,int k,int c)
{
int temp=1;
x=x%c;
while(k)
{
if(k%2==1)
temp=(temp*x)%c;
k=k/2;
x=(x*x)%c;
}
return temp;
}
int main()
{
int ans=1,i,j,a,b,k,n,m;
pangle[0][1]=1;
for(i=1;i<MAX;i++)
for(j=1;j<MAX+1;j++)
pangle[i][j]=(pangle[i-1][j]+pangle[i-1][j-1])%10007;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
ans*=power(a,n,10007);
ans*=power(b,m,10007);
ans=ans*pangle[k][m+1]%10007;
printf("%d",ans);
return 0;
}

who can tell me why

题目里给出的m没用吗？
我不会 去搜了个代码 发现他根本没用到m
但是AC了
谁能告诉我这是毛线定理
跪谢神犇

var
f:array[-1..1001,-1..1001] of int64;
a,b,m,n,k:int64;
i,j:longint;
begin
readln(a,b,k,n,m); m:=0;
f[1,0]:=b;
f[1,1]:=a;
for i:=2 to k do
for j:=0 to k do
f[i,j]:=(f[i-1,j]*b+f[i-1,j-1]*a) mod 10007;
writeln(f[k,n]);
end.

错了好多次啊
递推的
记录信息
评测状态 Accepted
题目 P1739 计算系数
递交时间 2015-10-20 22:37:06
代码语言 C++
评测机 VijosEx
消耗时间 60 ms
消耗内存 8292 KiB
评测时间 2015-10-20 22:37:12
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:29:19: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld",ans);
^
foo.cpp:29:19: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 0 ms, mem = 8260 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8260 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8260 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 8256 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 8256 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 8280 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 8280 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 8292 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 8288 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 8288 KiB, score = 10
Accepted, time = 60 ms, mem = 8292 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const long long mod=10007;
long long mem[1010][1010];
long long work(int n,int k)
{
if(n==k)return 1;
if(n==1)return k;
if(mem[n][k])return mem[n][k];
return mem[n][k]=(work(n,k-1)+work(n-1,k-1))%mod;
}
int main()
{
int a,b,k,n,m;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
long long ansx=1,ansy=1;
a%=mod;//这两句话不加就会爆两个点
b%=mod;
for(int i=n,x=a;i;x=(x*x)%mod,i>>=1)
if(i&1)ansx=(ansx*x)%mod;
for(int i=m,y=b;i;y=(y*y)%mod,i>>=1)
if(i&1)ansy=(ansy*y)%mod;
long long ans=(ansx*ansy)%mod;

ans=(ans*work(n,k))%mod;
printf("%lld",ans);
return 0;
}

#include<cstdio>
#include<algorithm>
#define mod 10007
using namespace std;

long long int num[2010][7000];

int main()
{
int a, b, k, n, m;
long long ans = 1;
scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
num[1][1] = num[1][2] = 1;
for(int i=2; i<=k; i++)
for(int j=1; j<=i+1; j++)
num[i][j] = (num[i-1][j-1]+num[i-1][j])%mod;
ans = num[k][m+1];
for(int i=1; i<=n; i++)
ans = (ans*a) % mod;
for(int j=1; j<=m; j++)
ans = (ans*b) % mod;
printf("%lld", ans);
return 0;
}
杨辉三角