逆元

[tipstar0125]

計算の途中で、割る操作をしたい ※有理数modを除く

• 割り切れることができれば、やってもよい。例えば、nCr modの分子は分母で割り切れるので、割る操作ができる
• 例えば、2で割りたい場合、実際の整数の計算では、奇数の時、切り捨てを期待するが、modintの条件下だと、それができない。分子が全て奇数の場合は、-1して偶数にしてから、2で割ることができる
• 最後だけ割る操作をする場合、mod P*(割る数)で計算後、割って、mod Pをとる（割る数をかけることで、その数で割れるかどうかの状態を保持できる）

https://atcoder.jp/contests/arc167/tasks/arc167_b https://atcoder.jp/contests/abc293/editorial/5966