Tayama https://blog.hatena.ne.jp/Tayama/ aizuzia https://tayama-2.hatenadiary.org/ Problem UVa 11651: Krypton Number System Problem B 0から始まらない どの隣り合う桁も異なる 隣り合う桁の差の2乗の総和が S ような数はいくつあるか？ mod 2^32 で。 Solution 問題は言い換えてみれば、 0 .. B-1 の数字をノードとし、2数の差の2乗を重みとするような辺を張ったグラフにおいて、1 .. B-1 のどれかから 0 .. B-1 へのどれかへの重み S であるようなパスの数を求めることと同値。なので、行列のN乗で計算できる。 重み付きグラフのままだとどうしたらいいものか分からなかったので、適当にダミーノードを挟んで強引に重み… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftayama-2.hatenadiary.org%2Fentry%2F20090912%2F1252777966" title=" UVa 11651 Krypton Number System - aizuzia" 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 2009-09-12 02:52:46 rich https://tayama-2.hatenadiary.org/entry/20090912/1252777966 1.0 100%