Combinatorics(組合せ数学) (combinatorics/combinatorics.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-02-24 11:32:00+09:00

なにこれ

${}_nP_r, {}_nC_r, {}_nH_r\ (\mathrm{mod}\ p)$ を求める．

コンストラクタ

• COMB(n, p)：$n$ の最大値を n，法を p とする．${}_nH_r$ を求める場合は $(n+r-1)$ の最大値を n とする．$n \leq 10^7$, $p \leq$ INT_MAX 程度．$p$ は素数．

メンバ関数

• npr(n, r)
• ncr(n, r)
• nhr(n, r)

計算量

• COMB(n, p)：$O(n)$
• npr(n, r)：$O(1)$
• ncr(n, r)：$O(1)$
• nhr(n, r)：$O(1)$

Verified with

• test/aoj_DPL_5_D.cpp
• test/yuki_0117.cpp
• test/yuki_1035.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct COMB {
private:
	vector<long long> fact, inv, finv;
	const long long P;

public:
	COMB(long long n, long long p) : fact(n + 1), inv(n + 1), finv(n + 1), P(p) {
		assert(P < (1 << 30) - 1);
		fact[0] = fact[1] = inv[1] = finv[0] = finv[1] = 1LL;
		for(long long i = 2LL; i <= n; i++) {
			fact[i] = fact[i - 1] * i % P;
			inv[i] = P - inv[P % i] * (P / i) % P;
			finv[i] = finv[i - 1] * inv[i] % P;
		}
	}

	long long npr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r > n) return 0;
		return fact[n] * finv[n - r] % P;
	}

	long long ncr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r > n) return 0;
		return fact[n] * finv[r] % P * finv[n - r] % P;
	}

	long long nhr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r == 0) return 1;
		if(n == 0) return 0;
		return ncr(n + r - 1, n - 1);
	}
};

#line 2 "combinatorics/combinatorics.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct COMB {
private:
	vector<long long> fact, inv, finv;
	const long long P;

public:
	COMB(long long n, long long p) : fact(n + 1), inv(n + 1), finv(n + 1), P(p) {
		assert(P < (1 << 30) - 1);
		fact[0] = fact[1] = inv[1] = finv[0] = finv[1] = 1LL;
		for(long long i = 2LL; i <= n; i++) {
			fact[i] = fact[i - 1] * i % P;
			inv[i] = P - inv[P % i] * (P / i) % P;
			finv[i] = finv[i - 1] * inv[i] % P;
		}
	}

	long long npr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r > n) return 0;
		return fact[n] * finv[n - r] % P;
	}

	long long ncr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r > n) return 0;
		return fact[n] * finv[r] % P * finv[n - r] % P;
	}

	long long nhr(long long n, long long r) {
		assert(n >= 0 && r >= 0);
		if(r == 0) return 1;
		if(n == 0) return 0;
		return ncr(n + r - 1, n - 1);
	}
};

Back to top page