This documentation is automatically generated by competitive-verifier/competitive-verifier
${}_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)$#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);
}
};