🐢
[鉄則A30] Combination (割り算→掛け算)
割り算を掛け算に変換する問題。
問題を要約する
- nCr の結果を 1000000007 で割った余りで出力せよ
何が難しいか？
1. combination メソッドは使えない
N が小さいと 1 秒以内で解けるが、
N = 4
N.times.to_a.combination(2).count.modulo(1000000007) # => 6
N = 10万 で固まってしまう。
N = 10_0000
N.times.to_a.combination(2).count.modulo(1000000007) # => ?
2. 割り算が含まれる
割り算が含まれる場合 1000000007 で丸めることができない。
要点
-
a / bとa * b**(MOD - 2)は同じ
つまり割り算を掛け算に変換できる。
ダメな実装 (RE)
N, R = gets.split.collect(&:to_i) # => [4, 2]
MOD = 1000000007
# nCr = n! / (r! * (n - r)!)
a = N.downto(2).reduce(:*) # n!
b = R.downto(2).reduce(:*) # r!
c = (N - R).downto(2).reduce(:*) # (n - r)!
d = b * c # r! * (n - r)!
p (a / d).modulo(MOD) # => 6
これは、
- 割り算が含まれるため MOD で丸めたら結果が変わる
-
N = 100000で固まる - 提出すると RE になる
などいろいろおかしい。
解説の模範解答 (AC)
121 ms
N, R = gets.split.collect(&:to_i) # => [4, 2]
MOD = 1000000007
# nCr = n! / (r! * (n - r)!)
a = N.downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # n!
b = R.downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # r!
c = (N - R).downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # (n - r)!
d = (b * c).modulo(MOD) # r! * (n - r)!
x = (a * d.pow(MOD - 2, MOD)).modulo(MOD) # n! / r! * (n - r)!
p x # => 6
a / d を a * d.pow(MOD - 2, MOD) に変換して割り算をなくしている。
Discussion