nCk mod mの計算（※mは素数とする）

TopCoder用コピペメモw

１つだけ求めたい場合

• x/y mod m をフェルマーの小定理で

typedef long long LL;

const LL MOD = 1000000007LL;

// LL add(LL x, LL y) { return (x + y) % MOD; }
// LL sub(LL x, LL y) { return (x - y) % MOD; }
LL mul(LL x, LL y) { return (x * y) % MOD; }
LL pow(LL x, LL y) {
  LL v = 1;
  for ( ; y; x=mul(x,x), y>>=1)
    if (y&1) v = mul(v, x);
  return v;
}
LL divi(LL x, LL y) { return mul(x, pow(y, MOD-2)); }
// ↑divって名前にしたいのもやまやまですが stdlib.h の div (3) と名前がかぶるのです

LL C(LL n, LL k) {
  LL v = 1; // nC0
  for (LL i=1; i<=k; ++i) 
    v = divi(mul(v, n-i+1), i); // nCi
  return v; // nCk
}

範囲が分かってるので先に計算しておける時

• 1≦n≦100, 0≦k≦n とかならパスカルの三角形をDPで先に作っておけばよい
• c[n][k] の値が nCk

const int C_MAX = 100;
vector<vector<LL> > c(C_MAX+1, vector<LL>(1, 1LL));
for (int i = 1; i <= C_MAX; ++i) {
  for (int j = 1; j < i; ++j) {
    LL c_ij = (c[i-1][j-1] + c[i-1][j]) % MOD;
    c[i].push_back(c_ij);
  }
  c[i].push_back(1);
}