AGC 034 F RNG and XOR
解説と全然違うことをして通したので書く。各ステップは難しくないが相当の考察腕力を必要とする。実装はほぼ無。
問題概要
最初 にいて、 上の確率変数 を xor していくランダムウォークを考える。各状態について、はじめてその状態に至るまでの遷移回数の期待値を求めよ。 からは全部の値が正の確率で出る
母関数による言い換え
遷移行列を とする。 を 番目の要素のみ であって他は であるようなベクトルとして、 とする。すなわち は時刻 に状態 にいる確率。この母関数を とする。
これらを用いて、時刻 に初めて状態 にいる確率 を求めていく。ただし、 に対しては は時刻 を除いて初めて時刻 に にいる確率とし、便宜上 とする。より正確には、この母関数 を求める。
に関しては漸化式 が立ち、 から を得る。 に対しては、 がやはり DP のようなことを考えると出てくるので、 を得る。まとめれば、 を得る。
さて、求めたい期待値は であった。これは、 を で一回微分したあと、 を代入すれば得られる。商の微分公式を用いれば、求めたい値は、 の での値である。
固有ベクトルへの分解
非負整数 に対し、母関数 の分子と分母の の係数を評価していく。このまま定義式を代入すると行列が入ってきて大変なので、 の固有ベクトルに を分解して考えることにする。 の固有ベクトルは 次 Hadamard 行列 (定数倍に関しては、係数はすべて とする) の各行に一致する。その 行目 (-origin) に対応する固有ベクトルを と書き、対応する固有値を とする。これを用いれば、 と書ける。
極限値の評価
の要素はすべて正なので、唯一の最大固有値は固有ベクトル に対応する である。よって、 を大きく取れば、 は に比べて無視できるようになることが期待できる。これを用いて、大きい に対する の係数を評価していく。
まずは簡単な分母の方から評価する。先ほどの の表式を求めたい式に代入し、主要項にならない項を無視すると、分母の係数は (主要項とそれにつく係数以外を無視して) となる。
分子に関しては、引き算によって に対応する項が消えるので、次の項も評価してやる必要がある。結局、計算すると展開式のうち主要項として残るのは の項となることが分かる。 を評価すると大きい に対して が主要項として残ることが分かる。よって、分子の係数は (主要項とそれにつく係数以外を無視して) となる。分子と分母の評価を合わせて での評価を行えば、結局求めたい値は であることが分かる。
答えの計算
さて、この値を計算することを考える。各固有値 の値は、与えられた確率の列を Hadamard 変換したものの第 要素そのものであり、高速 Hadamard 変換を用いて求められる。 としてできるベクトル を考える。 は、 を Hadamard 変換したものの第 要素に他ならないため、これも高速 Hadamard 変換で求められる。最後に、 は、上述の Hadamard 変換の第 要素である。このことから、この問題は、
・与えられた確率の列を高速 Hadamard 変換して各固有値を求め、
・上述の を計算し (ただの割り算)、
・ を高速 Hadamard 変換してできる列の第 要素から第 要素を引いた値を各 に対して出力する
というアルゴリズムを用いて解くことができる。