ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.117

愚直に順列・組み合わせ・重複組み合わせを求める問題.だが簡単ではない

※:PRIME = 1000000007は素数

詰まったところ

  1. a modpの逆元を求める部分.a^(p-2) = a^(-1)まではわかったのだが,それをO(PRIME)で書いてしまったところ.指数の偶奇で場合分けして書くとO(log(PRIME))で済みますね..
  2. REが連発した,おそらくサイズの大きい配列の初期化でf[2000000]と書いていたところが原因か?
  3. WAで引っかかった部分.重複組み合わせのn+k-1<0になる時の例外処理を忘れていた.

yukicoder No.117

こういう類のものは息をするように書けるようになると思考の余裕が大分出てきそう.