Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

CF2016Final-D Pair Cards 解説

問題

D - Pair Cards

解説

まず2枚組が作れる条件をぐっと睨みましょう, すると全てのカードの剰余を考えれば良いことが分かります.
つまりMでの剰余を考えると, 2つの数の和がMの倍数\rightarrow和のMで割ったあまりが0 という条件になるので簡単に数えることができるようになります.
次にもう1つの条件は各Mでの剰余に対し, 同じカードの組がいくつあるかを数え上げれば良いことが分かります.

これらを剰余で分類すれば後は数え上げるだけです.
これはまず和がMの倍数\rightarrow同じカード の順にGrundyをすれば最適です(証明はeditorialをみてください).

これで考察は終わりです, いい感じに実装しましょう.

コード

Submission #1920399 - CODE FESTIVAL 2016 Final (Parallel)

感想

これ実装グチャる.