AtCoder Regular Contest 102 E - Stop. Otherwise...
問題概要
互いに区別できないK面サイコロN個を振る際の任意の2つのサイコロの目の和がi(2≦i≦2*K)にならない組み合わせの数を各iに対し出力する。
解法
ちょっと考えると、出し得る目の数から2つのサイコロの目の和がiになるやつを引く事で答えが出るため、包除原理が使えそうだなあとなる。よって、
各iの偶奇によってi/2Ci*KHN-2を足し引きしてあげることで解けそう
制約が1≦N,K≦2000と緩いので上記を実装してあげて、AC*1
ただし、解説は包除原理使ってないっぽいのでむううとなった。
超余談
下の動画を昨夜見ながら考えてたら解けました(実装を朝に回したのでAC時間は朝)。ありがとうPewDiePie。ありがとうT-Series。しかも見始めた時よりもPewが差をつけているので個人的には嬉しい。
*1:nCrをもとめるのに逆元のやつのテンプレを使うと色々いいよねと言う話をしたい。
