C - タコヤ木 arc023_3

f:id:peroon:20190204231745j:plain

Quiz

https://atcoder.jp/contests/arc023/tasks/arc023_3

Submit

https://atcoder.jp/contests/arc023/submissions/4174678

補足

  • いつものフェルマーの小定理と逆元
    • ・・・と思ったらnCrのnが109まである。階乗を求めるだけでもTLEになるだろう
  • ポイントはrが小さくできること
  • nCrを全て階乗で表すのはやめて、5C2 = 5x4 / 2x1 のままで計算することでrの小ささを利用できる

参考

https://suikaba.hatenablog.com/entry/2017/08/16/010735