This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
/***** 最大公約数・最小公倍数 *****/
// gcd (2つの整数に関して、最大公約数)
int gcd(int a, int b) {
if(a < b) swap(a, b);
if(b == 0) return a;
return gcd(b, a%b);
}
// lcm (2つの整数に関して、最小公倍数) ※gcd実装前提
int lcm(int a, int b) {
return a * b / gcd(a,b);
}
// extgcd (ax + by = gcd(a,b) を満たすx,yを求める)
// xとyで参照を使用している
// (実引数で指定した変数の中身が関数によって書き換わる)
int extgcd(int a, int b, int& x, int& y) {
int d = a;
if(b!=0) {
d = extgcd(b, a%b, y, x);
y -= (a / b) * x;
}
else {
x = 1; y = 0;
}
return d;
}
// 逆元を求める (ax ≡ 1 (mod m) に対して、xを求める。) ※extgcd実装前提
int mod_inverse(int a, int m) {
int x,y;
extgcd(a,m,x,y);
return (m + x % m) % m; //正の整数を保証
}
/***** 組み合わせ関係 *****/
// combination O(N)
const int MAXN = 100010;
long long int fact[MAXN], inv[MAXN];
void init_fact() {
fact[0] = 1;
for(int i=1; i<MAXN; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
inv[MAXN - 1] = mod_pow(fact[MAXN - 1], MOD-2);
for(int i=MAXN - 2; i>=0; i--) {
inv[i] = (inv[i+1] * (i+1)) % MOD;
}
}
long long int comb(int n, int r) {
if(r < 0 || n < r) return 0;
return fact[n] * inv[n-r] % MOD * inv[r] % MOD;
}
// 繰り返し二乗法 (modの世界での累乗)
// ※modが素数の場合、この関数で(mod - 2)乗したら、mod割り算ができるよ!
// (参考問題: ABC034 C問題など)
ll mod_pow(ll x, ll n) {
ll res = 1;
while(n > 0) {
if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
x = (x * x) % MOD;
n >>= 1; //右シフト(n = n >> 1)
}
return res;
}
// 繰り返し二乗法 (再帰バージョン)
// typedef long long ll;
ll mod_pow(ll x, ll n) {
if(n == 0) return 1;
ll res = mod_pow((x * x) % MOD, n / 2);
if(n & 1) res = (res * x) % MOD;
return res;
}
// 組み合わせ nCr mod p を求める
ll combination_mod(ll n, ll r) {
if(n < r) return 0;
if(r == 0 || r == n) return 1;
ll a = fact[n];
ll b = fact[n-r];
ll c = fact[r];
ll x = a, y = (b * c) % MOD;
return ( x * mod_pow(y, MOD-2) ) % MOD;
}
// 組み合わせを求める (DP、パスカルの三角形)
const int SIZE = 5000;
ll comb[SIZE+10][SIZE+10];
comb[0][0] = 1;
for(int i=0; i<SIZE; i++) {
for(int j=0; j<SIZE; j++) {
(comb[i+1][j] += comb[i][j]) %= MOD;
(comb[i][j+1] += comb[i][j]) %= MOD;
}
}
#line 1 "math/math_001_mod.cpp"
/***** 最大公約数・最小公倍数 *****/
// gcd (2つの整数に関して、最大公約数)
int gcd(int a, int b) {
if(a < b) swap(a, b);
if(b == 0) return a;
return gcd(b, a%b);
}
// lcm (2つの整数に関して、最小公倍数) ※gcd実装前提
int lcm(int a, int b) {
return a * b / gcd(a,b);
}
// extgcd (ax + by = gcd(a,b) を満たすx,yを求める)
// xとyで参照を使用している
// (実引数で指定した変数の中身が関数によって書き換わる)
int extgcd(int a, int b, int& x, int& y) {
int d = a;
if(b!=0) {
d = extgcd(b, a%b, y, x);
y -= (a / b) * x;
}
else {
x = 1; y = 0;
}
return d;
}
// 逆元を求める (ax ≡ 1 (mod m) に対して、xを求める。) ※extgcd実装前提
int mod_inverse(int a, int m) {
int x,y;
extgcd(a,m,x,y);
return (m + x % m) % m; //正の整数を保証
}
/***** 組み合わせ関係 *****/
// combination O(N)
const int MAXN = 100010;
long long int fact[MAXN], inv[MAXN];
void init_fact() {
fact[0] = 1;
for(int i=1; i<MAXN; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
inv[MAXN - 1] = mod_pow(fact[MAXN - 1], MOD-2);
for(int i=MAXN - 2; i>=0; i--) {
inv[i] = (inv[i+1] * (i+1)) % MOD;
}
}
long long int comb(int n, int r) {
if(r < 0 || n < r) return 0;
return fact[n] * inv[n-r] % MOD * inv[r] % MOD;
}
// 繰り返し二乗法 (modの世界での累乗)
// ※modが素数の場合、この関数で(mod - 2)乗したら、mod割り算ができるよ!
// (参考問題: ABC034 C問題など)
ll mod_pow(ll x, ll n) {
ll res = 1;
while(n > 0) {
if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
x = (x * x) % MOD;
n >>= 1; //右シフト(n = n >> 1)
}
return res;
}
// 繰り返し二乗法 (再帰バージョン)
// typedef long long ll;
ll mod_pow(ll x, ll n) {
if(n == 0) return 1;
ll res = mod_pow((x * x) % MOD, n / 2);
if(n & 1) res = (res * x) % MOD;
return res;
}
// 組み合わせ nCr mod p を求める
ll combination_mod(ll n, ll r) {
if(n < r) return 0;
if(r == 0 || r == n) return 1;
ll a = fact[n];
ll b = fact[n-r];
ll c = fact[r];
ll x = a, y = (b * c) % MOD;
return ( x * mod_pow(y, MOD-2) ) % MOD;
}
// 組み合わせを求める (DP、パスカルの三角形)
const int SIZE = 5000;
ll comb[SIZE+10][SIZE+10];
comb[0][0] = 1;
for(int i=0; i<SIZE; i++) {
for(int j=0; j<SIZE; j++) {
(comb[i+1][j] += comb[i][j]) %= MOD;
(comb[i][j+1] += comb[i][j]) %= MOD;
}
}