Livedoorブログからの移動
はてなブログからの移動

arc077.contest.atcoder.jp

解き方

  • 重複を考えずに組み合わせを計算し，重複分を引く
    • 条件より重複は必ず1個存在する
  • 組み合わせの計算は，n!を事前に計算しておく事でO(1)で行う
    • n!^{-1}もmodを取る場合は前計算できる

ハマった所

  • 組み合わせ計算の高速化方法
    • n!の前計算は，逆数の前計算の方法が分からなかったのでコンテスト中はできなかった
    • 割り算の場合にも普通にmodをとってしまっていた（深く考えてなかった）
  • 重複計算のところで無駄なループをしていた
    • 組み合わせ計算に関するループ（積和計算のような）は削れる可能性高そう？