I have seen some similar functions in problems where numbers are large and we need to mod a number like 998244353 or 1000000007 (I also noticed they are all prime). I think this function might be modular inverse??? But I don't know why any of this works and how do I use it. I don't get why I need to decrease 2 from the mod number to make it work. I don't get what the dividing by two is about. Will very appreciate if someone can help. Thank you. +++↵
↵
[problem:1999F]↵
↵
~~~~~↵
const int N = 2e5 + 5, mod = 1e9 + 7;↵
int64_t fact[N];↵
int64_t pw(int64_t a, int64_t b) {↵
int64_t r = 1;↵
while(b > 0) {↵
if(b & 1) r = (r * a) % mod;↵
b /= 2;↵
a = (a * a) % mod; ↵
}↵
return r;↵
}↵
~~~~~↵
↵
[problem:2053D]↵
↵
~~~~~↵
int qpow(int a, int x = MOD — 2) {↵
int res = 1;↵
for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;↵
return res;↵
}↵
~~~~~↵
↵
↵
↵
↵
↵
[problem:1999F]↵
↵
~~~~~↵
const int N = 2e5 + 5, mod = 1e9 + 7;↵
int64_t fact[N];↵
int64_t pw(int64_t a, int64_t b) {↵
int64_t r = 1;↵
while(b > 0) {↵
if(b & 1) r = (r * a) % mod;↵
b /= 2;↵
a = (a * a) % mod; ↵
}↵
return r;↵
}↵
~~~~~↵
↵
[problem:2053D]↵
↵
~~~~~↵
int qpow(int a, int x = MOD — 2) {↵
int res = 1;↵
for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;↵
return res;↵
}↵
~~~~~↵
↵
↵
↵
↵
