标签归档:组合数

NOIP2011 -计算系数

题目链接:CH3601

通过逆元计算组合数.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int quickpow(int m,int n,int mod){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*m%mod;
    m=(ll)m*m%mod;
    n>>=1;
  }
  return res;
}

int factorial(int n,int mod){
      if(!n) return 1;
      int res=n%mod;
      while(--n){
        res=(ll)res*n%mod;
      }
      return res;
}

int main() {
  int a,b,n,m,k;
  const int mod=10007;
  cin>>a>>b>>k>>n>>m;
  a=quickpow(a,n,mod);
  b=quickpow(b,m,mod);
  int x=factorial(k,mod);
  int y1=factorial(n,mod);
  int y2=factorial(k-n,mod);
  y1=quickpow(y1,mod-2,mod);
  y2=quickpow(y2,mod-2,mod);
  int ans=(ll)y1*y2%mod*x%mod*a%mod*b%mod;
  cout<<ans<<endl;
  return 0;
}