ルーカスの定理 lucas リュカ 使った記録

• B-123 Triangle
  • https://atcoder.jp/contests/agc043/tasks/agc043_b
• AC
  • https://atcoder.jp/contests/agc043/submissions/24728675
• その他
  • 自分で作ったのはTLEしたりギリギリACしたり、意外とLucasの定理は時間がかかるようだった
  • algo-logicさんのを借りてくると2倍速くなったが、それでも1秒かかっていた
  • algo-logicさんのを使うといいよ https://algo-logic.info/binomial-coefficient-lucas/

制約

• nCr mod m にて、
• n, r <= 10¹⁸
• m <= 1000程度
• 理論的にはこれくらいはいけそう

発展

• m<=10⁶でもいけるみたい。さらにmは素数じゃなくてもよさそう？
• https://judge.yosupo.jp/problem/binomial_coefficient