两个知识点：
1. 数据巨大，不能等到求出结果再取余。a*b%c=(a%c)*(b%c)%c
2. 利用组合公式：c(n,m)=c(n-1,m)+c(n-1,m-1)
3. 记忆化，否则时间耗不起。
代码：
#include<fstream>
using namespace std;
const int N(10007);
int ans(1),c[1001][1001];
void f1(int x,int y)
{
for (int i=0;i<y;i++)
ans=ans*(x%N)%N;
}
int com(int n,int x)
{
if (c[n][x]!=-1) return c[n][x];
else
if (n==x||x==0) return c[n][x]=1;
else {
if (c[n-1][x-1]==-1) c[n-1][x-1]=com(n-1,x-1)%N;
if (c[n-1][x]==-1) c[n-1][x]=com(n-1,x)%N;
return c[n][x]=(c[n-1][x-1]+c[n-1][x])%N;
}
}
int main()
{
ifstream cin("factor.in");
ofstream cout("factor.out");
int a,b,k,n,m;
cin>>a>>b>>k>>n>>m;
f1(a,k-m);
f1(b,m);
m=min(m,k-m);
for (int i=0;i<=k;i++)
for (int j=0;j<=i;j++)
c[i][j]=-1;
ans=ans*com(k,m)%N;
cout<<ans<<endl;
cin.close();
cin.close();
return 0;
}
posted on 2012-05-30 16:14
龙在江湖 阅读(465)
评论(0) 编辑 收藏 引用 所属分类:
竞赛题解_NOIP