const long long Mod=10007;
cin>>a>>b>>k>>n>>m;
c[0]=1;
for (int i=1;i<=k;++i) {
c[i]=c[i-1]*(k-i+1)/i;
}
c[m]%=Mod;
cout<<(c[m]*qmod(a,k-m)*qmod(b,m))%Mod;

var
a,b,k,n,m,i,j,mu,di:longint;
c:int64;
q:array[2..1000] of longint;

function min(a,b:longint):longint;
begin
if a<=b then exit(a)
else exit(b);
end;

begin
readln(a,b,k,n,m);
c:=1;

for i:=1 to min(n,k-n) do
begin
mu:=k-i+1;di:=i;

for j:=2 to mu do
while (mu<>1) and (mu mod j=0) do
begin
inc(q[j]);
mu:=mu div j;
end;

for j:=2 to di do
while (di<>1) and (di mod j=0) do
begin
dec(q[j]);
di:=di div j;
end;

end;

for i:=2 to 1000 do
if q[i]<>0 then
for j:=1 to q[i] do
c:=c*i mod 10007;

for i:=1 to n do
c:=c*a mod 10007;

for i:=1 to m do
c:=c*b mod 10007;

writeln(c);
end.

var
a,b,k,n,m,i:longint;
c:int64;

begin
readln(a,b,k,n,m);
c:=1;

for i:=1 to n do
c:=(c*(k-i+1) div i) mod 10007;

for i:=1 to n do
c:=c*a mod 10007;

for i:=1 to m do
c:=c*b mod 10007;

writeln(c);
end.

C++:

#include <cstdio>
#define MOD 10007
using namespace std;
int a,b,k,n,m;
int Pow(int x,int exp)
{
int ans=1,t=x%MOD;
while (exp)
{
if (exp&1) (ans*=t)%=MOD;
(t*=t)%=MOD;
exp>>=1;
}
return ans;
}
int Get_Inv(int x)
{
return Pow(x,MOD-2);
}
//C(m,n)=m!/(m-n)!/n!
int C(int m,int n)
{
int ans=1;
for (int i=m-n+1;i<=m;i++)
(ans*=i)%=MOD;
for (int i=2;i<=n;i++)
(ans*=Get_Inv(i))%=MOD;
return ans;
}
int main()
{
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
int ans=C(k,n);
(ans*=Pow(a,n))%=MOD;
(ans*=Pow(b,m))%=MOD;
printf("%d\n",ans);
getchar();getchar();
return 0;
}
不用
long long

............

换成long long后终于过了

这是我的代码，由于不知道怎么快速的求c（n，k）（囧呀，不过），所以我采取了一种笨方法——分解质因数，然后将c（n，k）转换为了一些质因数幂的乘积
这是我的代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 10007
const int max_k = 2001;
const int max_pr = 400;

short a[max_k];
int prime_list[max_pr],r;
int time[2][max_pr];

int f(int a)
{
if (a <= 1) return 1;
if (a >= M) return 0;
return (a*f(a-1))%M;
}

void get_prmls()
{
int i,j;
memset(a,1,sizeof(a));
r = a[0] = a[1] = 0;
for (i = 2;i < max_k;i++) {
if (a[i]) {
prime_list[r++] = i;
for (j = 2;i*j < max_k;j++)
a[i*j] = 0;
}
}
}

int power(int n,int a) // cal n^a
{
int static t;
if (a == 0) return 1;
if (n > M) return power(n%M,a);
if (a == 1) return n;
if (a&1) {
t = power(n,a>>1);
t = ((t*t)%M*n)%M;
return t;
} else {
t = power(n,a>>1);
t = (t*t)%M;
return t;
}
}

void factor(int a,int *time)
{
int static d;
for (d = 0;d < r;d++) {
while (a%prime_list[d] == 0) {
a /= prime_list[d];
*time = *time+1;
}
time++;
}
}

int c(int n,int r)
{
int i,ans;
memset(time,0,sizeof(time));
get_prmls();
for (i = n;i >= n-r+1;i--)
factor(i,time[0]);
for (i = 2;i <= r;i++)
factor(i,time[1]);
for (i = 0,ans = 1;i < max_pr;i++)
ans = (ans*power(prime_list[i],time[0][i]-time[1][i]))%M;
return ans;
}

int main()
{
int n,m,k,a,b,ans;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
ans = c(k,n);
ans = (ans*power(a,n))%M;
ans = (ans*power(b,m))%M;
printf("%d",ans);
return 0;
}

朴素的杨辉三角可以秒，10行代码，注意是N,M不是M,N，第一次看错竟然还有60分= =

这道题有三种解法：
1.用递推式c(n,m)=c(n-1,m)+c(n-1,m-1)求解O(n log n)
2.在求解直接用公式，时对乘数分解质因数，贮存质因数的个数，对分数分解质因数，减去相应的个数。O(n log n)
3.逆元求C(k,m),O(n)

代码（第一种思路）：
#include <cstdio>
#define MAXN 1001
#define rep(i,x) for (int i=0;i<x;i++)
#define MAX 10007
#define inf 0x7fffffff
int n,m,a,b,k,ans;
int c[MAXN][MAXN];
int C(int N,int M){
if (c[N][M]<inf) return c[N][M];
if (N==M||M==0) return 1;
if (N<M) return 0;
return c[N][M]=(C(N-1,M)+C(N-1,M-1))%MAX;
}
int main(){
rep(i,MAXN)rep(j,MAXN)c[i][j]=inf;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
ans=C(k,m);
rep(i,n) ans*=(a%MAX),ans%=MAX;
rep(i,m) ans*=(b%MAX),ans%=MAX;
printf("%d\n",ans);
return 0;
}

var x:array[0..3000,0..3000]of longint;{(ax+by)^k--x^n*y^m}
c,sx,sy,s,f,f1,f2,a,b,k,n,m:longint;
begin
{assign(input,'factor.in');
reset(input);
assign(output,'factor.out');
rewrite(output);}
read(a,b,k,n,m);
a:=a mod 10007;
b:=b mod 10007;
sx:=1;sy:=1;
for f:=1 to n do sx:=(sx*a) mod 10007;
for f:=1 to m do sy:=(sy*b) mod 10007;
s:=(sx*sy) mod 10007;//writeln(s);
x[1,1]:=1;
for f:=2 to k+1 do
for f1:=1 to f do
begin
x[f,f1]:=x[f,f1] mod 10007;
x[f-1,f1-1]:=x[f-1,f1-1]mod 10007; // begin
x[f,f1]:=x[f-1,f1]+x[f-1,f1-1]mod 10007;// write(x[f,f1]);end;
end;
x[k+1,1+k-n]:=x[k+1,k+1-n]mod 10007;
s:=s*x[k+1,1+k-n]mod 10007;
write(s mod 10007);
{close(input);
close(output);}
end.

var x:array[0..3000,0..3000]of longint;{(ax+by)^k--x^n*y^m}
c,sx,sy,s,f,f1,f2,a,b,k,n,m:longint;
begin
assign(input,'factor.in');
reset(input);
assign(output,'factor.out');
rewrite(output);
read(a,b,k,n,m);
a:=a mod 10007;
b:=b mod 10007;
sx:=1;sy:=1;
for f:=1 to n do sx:=(sx*a) mod 10007;
for f:=1 to m do sy:=(sy*b) mod 10007;
s:=(sx*sy) mod 10007;//writeln(s);
x[1,1]:=1;
for f:=2 to k+1 do
for f1:=1 to f do
begin
x[f,f1]:=x[f,f1] mod 10007;
x[f-1,f1-1]:=x[f-1,f1-1]mod 10007; // begin
x[f,f1]:=x[f-1,f1]+x[f-1,f1-1]mod 10007;// write(x[f,f1]);end;
end;
x[k+1,1+k-n]:=x[k+1,k+1-n]mod 10007;
s:=s*x[k+1,1+k-n]mod 10007;
write(s mod 10007);
close(input);
close(output);
end.

快速幂救世界

c++：

#include

using namespace std;

long p=10007;

long long result;

long long fast (long x,long n)

{

result = 1;

long y=x;

while (n>0)

{

if (n%2==1) result=result*y %p;

y=y * y % p;

n = n /2;

}

return result;

｝

int main() {

long a,b,n,m,k;

cin>>a>>b>>k>>n>>m;

long long tmp= fast(a,n);;

long long tmp2=fast(b,m);

long long tmp3=1;

long i;

for (i=1 ; i

数组要int64 不然会挂 悲剧*2

编译通过...

├ 测试数据 01：答案正确... (0ms, 5320KB)

├ 测试数据 02：答案正确... (0ms, 5320KB)

├ 测试数据 03：答案正确... (0ms, 5320KB)

├ 测试数据 04：答案正确... (0ms, 5320KB)

├ 测试数据 05：答案正确... (0ms, 5320KB)

├ 测试数据 06：答案正确... (0ms, 5320KB)

├ 测试数据 07：答案正确... (0ms, 5320KB)

├ 测试数据 08：答案正确... (0ms, 5320KB)

├ 测试数据 09：答案正确... (0ms, 5320KB)

├ 测试数据 10：答案正确... (0ms, 5320KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 5320KB

组合可以秒杀

就是IGNORE说的酷似DP方程的组合性质

类似杨辉

代码 十行

f[1,0]:=a;f[0,1]:=b;

for i:=1 to k do

begin

f:=(f*a)mod 10007;

f[0,i+1]:=(f[0,i]*b)mod 10007;

for j:=1 to i do

f[j,i-j+1]:=(f[j,i-j]*b+f[j-1,i-j+1]*a)mod 10007;

end;

方法同楼上,用递归不过是记忆化搜索

去年做这题时根本没学过组合数……还想到了杨辉三角……

现在我们知道组合数有个十分优美的性质，酷似DP方程：

C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m){2