nCr mod p ($n > p$) (combinatorics/small_p_ncr.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-04-20 01:50:41+09:00

なにこれ

${}_nC_r\ (\mathrm{mod}\ p)$ を求める．$n > p$ でも動く．

コンストラクタ

• spncr(n, p)：$n$ の最大値を n，法を p とする．$p$ は素数．

メンバ関数

• operator()(n, r)

計算量

• コンストラクタ：$O(n+p)$
• operator()(n, r)：$O(1)$

---

Verified with (AtCoder)

• arc117_c

Verified with

• test/atc_arc117_c.cpp

Code

#pragma once

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

struct spncr {
private:
	vector<long long> pnum, excp, inv;
	const long long P;

public:
	spncr(int n, int p) : pnum(n + 1), excp(n + 1), inv(p), P(p) {
		int tmp;
		pnum[0] = 0;
		excp[0] = 1;
		for(int i = 1; i <= n; i++) {
			tmp = i;
			pnum[i] = pnum[i - 1];
			while(tmp % p == 0) pnum[i]++, tmp /= p;
			excp[i] = excp[i - 1] * tmp % p;
		}

		inv[1] = 1;
		for(int i = 2; i < p; i++) inv[i] = P - inv[P % i] * (P / i) % P;
	}

	long long operator()(int n, int r) {
		assert(n >= 0 && r >= 0);
		if(r > n || pnum[n] - pnum[r] - pnum[n - r] > 0) return 0;
		return excp[n] * inv[excp[r] * excp[n - r] % P] % P;
	}
};

#line 2 "combinatorics/small_p_ncr.cpp"

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

struct spncr {
private:
	vector<long long> pnum, excp, inv;
	const long long P;

public:
	spncr(int n, int p) : pnum(n + 1), excp(n + 1), inv(p), P(p) {
		int tmp;
		pnum[0] = 0;
		excp[0] = 1;
		for(int i = 1; i <= n; i++) {
			tmp = i;
			pnum[i] = pnum[i - 1];
			while(tmp % p == 0) pnum[i]++, tmp /= p;
			excp[i] = excp[i - 1] * tmp % p;
		}

		inv[1] = 1;
		for(int i = 2; i < p; i++) inv[i] = P - inv[P % i] * (P / i) % P;
	}

	long long operator()(int n, int r) {
		assert(n >= 0 && r >= 0);
		if(r > n || pnum[n] - pnum[r] - pnum[n - r] > 0) return 0;
		return excp[n] * inv[excp[r] * excp[n - r] % P] % P;
	}
};

Back to top page