nCk mod mの計算(※mは素数とする)
TopCoder用コピペメモw
1つだけ求めたい場合
- 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); }