https://atcoder.jp/contests/abc151/tasks/abc151_e
二項係数の高速化が必要なので復習を(今回はpが素数で)
まず、二項係数の計算を割り算ではなく、-1乗(逆元)としてnCk ＝ n! * (𝑘!)−1 * ((𝑛−𝑘)!)−1として計算する。
また、このとき逆元を利用する必要がある。
mod p における a の逆元 x を求めるために、拡張ユークリッドの互除法を使う
ax≡1(modp)としたときのxがaの逆元(mod p)。 よって、
ax+py=1の解(x, y)を拡張ユークリッドの互除法により解(x, y)を求める。→xがaの逆元になっている
これは、ax+py=1が(mod p)で、ax≡1となるから。
よって、xを求めることが逆元を求めるに等しい。
こんな感じで逆元を求めれば良い。
ただ、階乗の逆元を求めるのがやばいので、逆元テーブルを作るような方法が良い。
この問題に関してはここまでやれればokだったので一区切り。
余談だが、python、今ならpow(x,-1,mod)で逆元求められるかも(計算量がどうかは知らない)
