剰余と組合せを安全に扱う
答えを M で割った余りで求める問題では、加算・乗算の途中でも余りを取れます。除算は普通の整数除算とは別です。
言語：Python / 計算量：二分累乗 O(log p)
前提：最大公約数とユークリッドの互除法 / DPは「同じ続きをまとめる」
考え方
- (a+b)%M、(a*b)%M は途中で余りを取っても一致。
- 素数 p で a が0でないなら a の逆元は pow(a,p-2,p)。
- n! が p の倍数になると、その階乗の逆元は使えません。
具体例
mod 7 では3の逆元は5。3×5=15≡1。2/3 に相当する値は2×5≡3です。
実装
p=7
inv=pow(3,p-2,p)
print(2*inv%p)注意する条件
(a//b)%p は a×逆元(b)%p と同じではありません。逆元が存在する条件は gcd(b,p)=1。
確認問題
mod 7 で3の逆元は？
解答と理由
5
3×5=15 は7で割ると1余ります。
実装課題
N K (0 ≤ K ≤ N ≤ 200000) に対する二項係数を 998244353 で割った余りを求める。
入力:
5 2
出力:
10参考実装
n,k=map(int,input().split())
p=998244353
f=[1]*(n+1)
for i in range(1,n+1):f[i]=f[i-1]*i%p
print(f[n]*pow(f[k]*f[n-k]%p,p-2,p)%p)