だいたいの二項係数modを解けるライブラリ(制作中)
使い方(簡易)
code:cpp
Binom<ll, 200010, Normal, 998244353> binom;
というように宣言して、
code:cpp
binom.C(n, k);
というように使う。
使い方(詳細)
Binomコンストラクタの引数は「型、大きさ、モード、mod」の順に渡す。
大きさやmodはモードによっては不要。以下の説明をご覧ください。
出来ること
Normal : $ N, K \leq 10^7程度で$ _NC_K \bmod \ Pを求める。$ Pは$ \mathrm{max}(N, K)を超える素数である必要がある。
前計算$ Ο(\mathrm{max}(N, k))
各計算$ Ο(1)
大きさには$ Nの最大値を与える。
$ _NC_K, _NH_K, _NP_Kを求められる。
LargeN : $ N \leq 10^9, K \leq 10^7程度で$ _NC_K \bmod \ Pを求める。$ Pは$ \mathrm{max}(N, K)を超える素数である必要がある。
前計算$ Ο(K)
各計算$ Ο(K)
大きさには$ Kの最大値を与える。
$ _NC_K, _NH_K, _NP_Kを求められる。
LargeNLocked : $ N \leq 10^9, K \leq 10^7程度で$ _NC_K \bmod \ Pを求める。$ Pは$ \mathrm{max}(N, K)を超える素数である必要がある。また、$ Nは変化しないことが必須条件。
前計算$ Ο(K)
各計算$ Ο(1)
大きさには$ Kの最大値を与える。
$ _NC_K, _NP_Kを求められる。
Pascal : $ N \leq 5000程度で$ _NC_K \bmod \ Pを求める。$ Pが素数である必要はない。
前計算$ Ο(N^2)
各計算$ Ο(1)
大きさには$ Nの最大値を与える。
$ _NC_Kを求められる。
AnyP : $ N, K \leq 10^{18}, P \leq 10^6程度で$ _NC_K \bmod \ Pを求める。$ Pが素数である必要はない。
前計算 $ 0
各計算 わからない……
大きさには何も与えなくてよい。
modが定数でかつリテラルとして与えられるならばそのまま与える。
modがリテラルとして与えられない、変更される、といった場合は適当に値を与えておき、giveModを呼び出す。引数にmodを与える。
$ _NC_Kを求められる。
なお、明記がない場合の計算量は時間、空間ともに表記された値である。
未実装
何か知らないけどLibrary Checkerのあれは通らない
ちゃんと調べて作る
code:cpp
enum BinomType{
Normal,
LargeN,
LargeNLocked,
Pascal,
AnyP
};
template<typename S, int L, BinomType B, int mod>
class Binom{
public:
Binom(int n = 1000000000){
if(B == BinomType(Normal)){
fac.assign(L, 0);
finv.assign(L, 0);
inv.assign(L, 0);
for(int i = 2; i < L; i++){
invi = mod - invmod % i * (mod / i) % mod; }
}else if(B == BinomType(LargeN)){
inv.assign(L, 0);
for(int i = 2; i < L; i++){
invi = mod - invmod % i * (mod / i) % mod; }
}else if(B == BinomType(LargeNLocked)){
inv.assign(L, 0);
for(int i = 2; i < L; i++){
invi = mod - invmod % i * (mod / i) % mod; }
c_ans.assign(L, 0);
for(int i = 2; i < L; i++){
c_ansi = c_ansi - 1 * ((n - i + 1) * invi % mod) % mod; }
p_ans.assign(L, 0);
for(int i = 2; i < L; i++){
p_ansi = p_ansi - 1 * (n - i + 1) % mod; }
}else if(B == BinomType(Pascal)){
pascal.resize(L);
for(int i = 0; i < L; i++) pascali.resize(L); for(int i = 1; i < L; i++){
for(int j = 1; j < L; j++){
}
}
}else if(B == BinomType(AnyP)){
// nothing to initialize
pmod = n;
}else{
// not implemented
exit(EXIT_FAILURE);
}
}
void giveMod(int mod){
pmod = mod;
}
S C(int n, int k){
if(n < k) return 0;
if(n < 0 || k < 0) return 0;
if(B == BinomType(Normal)){
return S(facn * (finvk * finvn - k % mod) % mod); }else if(B == BinomType(LargeN)){
S ans = 1;
for(int i = 1; i <= k; i++){
ans = ans * ((n - i + 1) * invi % mod) % mod; }
return ans;
}else if(B == BinomType(LargeNLocked)){
}else if(B == BinomType(Pascal)){
}else if(B == BinomType(AnyP)){
long long x = pmod;
vector<long long> a, m;
for(int i = 2; i <= pmod; i++){
if(x % i == 0){
long long cnt = 0, pr = 1;
while(x % i == 0){
x /= i;
cnt++;
pr *= i;
}
makeFact(i, cnt);
a.push_back(C_sub(n, k, i, cnt));
m.push_back(pr);
}
}
return crt(a, m).first;
}else{
// not implemented
exit(EXIT_FAILURE);
}
}
S C(int k){
if(k < 0) return 0;
if(B == BinomType(LargeNLocked)){
}else{
exit(EXIT_FAILURE);
}
}
S C_sub(long long n, long long r, long long p, long long q){
if(n < 0 || r < 0 || r > n) return 0;
int pr = 1;
for(int i = 0; i < q; i++) pr *= p;
long long z = n - r;
int e0 = 0;
for(long long u = n / p; u; u /= p) e0 += u;
for(long long u = r / p; u; u /= p) e0 -= u;
for(long long u = z / p; u; u /= p) e0 -= u;
int em = 0;
for(long long u = n / pr; u; u /= p) em += u;
for(long long u = r / pr; u; u /= p) em -= u;
for(long long u = z / pr; u; u /= p) em -= u;
S ret = 1;
while(n > 0){
n /= p;
r /= p;
z /= p;
}
(ret *= binpow(p, e0, pr)) %= pr;
if(!(p == 2 && q >= 3) && em % 2) ret = (pr - ret) % pr;
return ret;
}
S H(int n, int k){
if(B == BinomType(LargeNLocked)){
exit(EXIT_FAILURE);
}
if(n < 0 || k < 0) return 0;
return C(n + k - 1, k);
}
S P(int n, int k){
if(n < k) return 0;
if(n < 0 || k < 0) return 0;
if(B == BinomType(Normal)){
return S(facn * finvn - k % mod); }else if(B == BinomType(LargeN)){
S ans = 1;
for(int i = 1; i <= k; i++){
ans = ans * (n - i + 1) % mod;
}
return ans;
}else if(B == BinomType(LargeNLocked)){
}else{
// not implemented
exit(EXIT_FAILURE);
}
}
S P(int k){
if(k < 0) return 0;
if(B == BinomType(LargeNLocked)){
}else{
exit(EXIT_FAILURE);
}
}
private:
vector<S> fac;
vector<S> finv;
vector<S> inv;
vector<S> c_ans, p_ans;
vector<vector<S>> pascal;
int pmod;
long long binpow(long long x, long long e, long long me){
long long a = 1, p = x;
while(e > 0){
if(e%2 == 0){
p = (p * p) % me;
e /= 2;
}else{
a = (a * p) % me;
e--;
}
}
return a % me;
}
long long extgcd(long long a, long long b, long long &x, long long &y){
long long g = a;
x = 1, y = 0;
if(b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
return g;
}
long long inverse(long long a, long long n){
long long s, t;
extgcd(a, n, s, t);
return (n + s) % n;
}
void makeFact(long long p, long long q){
long long pr = 1;
for(int i = 0; i < q; i++) pr *= p;
fac.assign(pr + 1, 0);
finv.assign(pr + 1, 0);
for(int i = 1; i <= pr; i++){
if(i % p == 0){
}else{
}
finvi = inverse(faci, pr); }
}
pair<long long, long long> crt(long long a1, long long a2, long long m1, long long m2){
auto normal = [](long long x, long long m){
return x >= -x ? x % m : m - (-x) % m;
};
auto modmul = &normal(long long a, long long b, long long m){ return normal(a, m) * normal(b, m) % m;
};
long long k1 = 0, k2 = 0;
long long g = extgcd(m1, m2, k1, k2);
if(normal(a1, g) != normal(a2, g)) return {-1, -1};
long long l = m1 / g * m2;
long long x = a1 + modmul(modmul((a2 - a1) / g, k1, l), m1, l);
return {x, l};
}
pair<long long, long long> crt(vector<long long> a, vector<long long> m){
long long me = 1, ans = 0;
int n = a.size();
for(int i = 0; i < n; i++){
tie(ans, me) = crt(ans, ai, me, mi); if(ans == -1) return {-1, -1};
}
return {ans, me};
}
};