Quiz
https://atcoder.jp/contests/abc066/tasks/arc077_b
Submit
https://atcoder.jp/contests/abc066/submissions/3919723
要素
- 問題を上手く捉え、重複した値で挟まれていない箇所の組み合わせで求める
- 解説pdf参照
- nCrなる組み合わせを求めるが、n=100000まであり得るので
- 値が大きい
- 計算量が多い
- kそれぞれに組み合わせを求める必要がある。高速化が必要
- modで割っていい時、フェルマーの小定理から逆元が求められる
- 逆元を求めるとき、(n!)1000000005を求めたりする
- それを高速に求めるための、二分累乗法
- nCrにてn=1, r=2などもあり得るのでその時は0を返す必要があった
- ・・・などなど、色々新しい要素があって大変だった。ACして報われた
