UVa 11651 Krypton Number System

Problem

B <= 6進数で
0から始まらない
どの隣り合う桁も異なる
隣り合う桁の差の2乗の総和が S <= 10^9 に等しい

ような数はいくつあるか？ mod 2^32 で。

Solution

問題は言い換えてみれば、 0 .. B-1 の数字をノードとし、2数の差の2乗を重みとするような辺を張ったグラフにおいて、1 .. B-1 のどれかから 0 .. B-1 へのどれかへの重み S であるようなパスの数を求めることと同値。なので、行列のN乗で計算できる。
重み付きグラフのままだとどうしたらいいものか分からなかったので、適当にダミーノードを挟んで強引に重み無しグラフに変換してから行列に落としました。行列のサイズが180ぐらいになってTLEをもらったので、行列が疎であることに目を付け、行列の乗算の

REP(i,n) REP(j,n) REP(k,n) c[i][j]+=a[i][k]*b[k][j];

を

REP(k,n) REP(i,n) if(a[i][k]) REP(j,n) if(b[k][j]) c[i][j]+=a[i][k]*b[k][j];

としたらギリギリ (4.800 / 5.000sec)で通りました。

あんまりスマートな解法じゃないです。行列のN乗をまだまだ使いこなせてない(実際、「重み無しグラフの長さNのパスの数」しか知らない)ので、要勉強です。
あと、行列N乗もちゃんとライブラリにしておこう。いつもどこかでしくじるので。

ところで、modをとるところはビット演算していたのだけれど、そもそもunsigned intで計算してれば何もする必要が無かったことに今になって気付きました。

追記 (20090915)

行列 N 乗をライブラリにしてみました。アドホックに書いたものと比べると随分短くなり、どうやらパフォーマンスも向上したっぽいです。満足。