semiexp https://blog.hatena.ne.jp/semiexp/ Algorithmer’s note https://semiexp.hatenadiary.org/ Algorithm TopCoder 問題 N*Nのボードがあり、色の異なるチェッカーがある。色iのチェッカーはcheckers[i]個ある。回転させて重なる配置を同じ配置と考えるとき、何通りの異なる配置があるか。 解法 90°回転で重なるものがA通り、180°回転で重なる(かつ90°回転で重ならないもの)がB通り、180°回転でも重ならないものがC通りあるとき、A+B/2+C/4通りが答えである。 C(a,b)を求めるのが必要でかつけっこう大変であるが、1234567891が素数のため、予め1〜100000について逆元を求めておけばC(a,b)はすぐに求まる。 回転によって重なるものの数は、どのマスの状態が一致しないといけないか… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsemiexp.hatenadiary.org%2Fentry%2F20110925%2F1316937603" title="TopCoder SRM423 Div1Hard - Algorithmer’s note" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-09-25 17:00:03 rich https://semiexp.hatenadiary.org/entry/20110925/1316937603 1.0 100%