When I was solving AtCoder's past questions (ABC145 --D), I had a hard time finding nCk mod p. Therefore, How to find the binomial coefficient (nCk mod. P) and inverse element (a ^ -1 mod. P) that are often done I'm going to leave the easy-to-use ModCombination class here, which is a rewrite of.
class ModCombination
def initialize(max)
@MOD = 10 ** 9 + 7
@fact = [1, 1]
@factinv = [1, 1]
@inv = [0, 1]
2.upto(max) do |i|
@fact << @fact[i-1] * i % @MOD
@inv << @MOD - @inv[@MOD % i] * (@MOD / i) % @MOD
@factinv << @factinv[i-1] * @inv[i] % @MOD
end
end
def com(n, k)
return 0 if n < k
return 0 if n < 0 || k < 0
return @fact[n] * (@factinv[k] * @factinv[n-k] % @MOD) % @MOD
end
end
--Rewrite the value of @MOD if MOD is other than $ 10 ^ 9 + 7 $
--com (n, k) gives nCk% MOD
max = 10 ** 6
comb = ModCombination.new(max)
puts comb.com(n, k) # nCk mod 10 ** 9 + 7
I'll omit it because I think it will come out if I check what the above code is doing. I hope this article leads to someone's AC.
Recommended Posts