AGC 034 F RNG and XOR

解説と全然違うことをして通したので書く。各ステップは難しくないが相当の考察腕力を必要とする。実装はほぼ無。

 

問題概要

最初  0 にいて、 \{0,1,...,2^N-1\} 上の確率変数  X を xor していくランダムウォークを考える。各状態について、はじめてその状態に至るまでの遷移回数の期待値を求めよ。 N \leq 18, X からは全部の値が正の確率で出る

 

母関数による言い換え

遷移行列を  A とする。 e _ j j 番目の要素のみ  1 であって他は  0 であるようなベクトルとして、 q _ {j,k} = e _ jA^ke _ 0 とする。すなわち  q _ {j,k} は時刻  k に状態  j にいる確率。この母関数を  q _ j(x)=\sum _ {k=0}^{\infty} q _ {j,k}x^k とする。

 

これらを用いて、時刻  k に初めて状態  j にいる確率  p _ {j,k} を求めていく。ただし、 j=0 に対しては  p _ {0,k} は時刻  0 を除いて初めて時刻  k 0 にいる確率とし、便宜上  p _ {0,0}=-1 とする。より正確には、この母関数  p _ j(x)=\sum _ {k=0}^{\infty} p _ {j,k}x^k を求める。

 

 j=0,k \geq 1 に関しては漸化式  \sum _ {i=0} ^ {k} p _ {0,i}q _ {0,k-i} = 0 が立ち、 p _ {0,0} = -1, q _ {0,0} = 1 から  p _ 0(x)q _ 0(x)=-1 を得る。 j\neq 0 に対しては、 p _ {j,k}=-\sum _ {i=0} ^ {k} p _ {0,i}q _ {j,k-i} がやはり DP のようなことを考えると出てくるので、 p _ j(x)=-p _ 0(x)q _ j(x) を得る。まとめれば、 p _ j(x)=\frac{q _ j(x)}{q _ 0(x)} を得る。

 

 さて、求めたい期待値は  \sum _ {k=0}^{\infty}kp _ {j,k} であった。これは、 p _ j(x) x で一回微分したあと、 x=1 を代入すれば得られる。商の微分公式を用いれば、求めたい値は、 \frac{q _ j(x)'q _ 0(x)-q _ j(x)q _ 0(x)'}{q _ 0(x)^2} x=1 での値である。

 

固有ベクトルへの分解

非負整数  t に対し、母関数  \frac{q _ j(x)'q _ 0(x)-q _ j(x)q _ 0(x)'}{q _ 0(x)^2} の分子と分母の  x^t の係数を評価していく。このまま定義式を代入すると行列が入ってきて大変なので、 A固有ベクトル e _ 0 を分解して考えることにする。 A固有ベクトル 2^N 次 Hadamard 行列 (定数倍に関しては、係数はすべて  1,-1 とする) の各行に一致する。その  i 行目 ( 0-origin) に対応する固有ベクトル h _ i と書き、対応する固有値 \lambda _ i とする。これを用いれば、 q _ {j,k} = e _ jA^ke _ 0 = \frac{1}{2^N}e _ j\sum _ {i = 0}^{2^N-1}\lambda _ i ^k h _ i = \frac{1}{2^N}\sum _ {i = 0}^{2^N-1}\lambda _ i ^k h _ {i,j} と書ける。

 

極限値の評価

 A の要素はすべて正なので、唯一の最大固有値固有ベクトル  h _ 0=(1,1,...,1) に対応する  1 である。よって、 k を大きく取れば、 \lambda _ i ^k (i\neq 0) \lambda _ 0 ^k に比べて無視できるようになることが期待できる。これを用いて、大きい  t に対する  x^t の係数を評価していく。

 

まずは簡単な分母の方から評価する。先ほどの  q _ {j,k} の表式を求めたい式に代入し、主要項にならない項を無視すると、分母の係数は (主要項とそれにつく係数以外を無視して)  \frac{1}{2^{2N}}\times t となる。

 

分子に関しては、引き算によって  \lambda _ 0^t に対応する項が消えるので、次の項も評価してやる必要がある。結局、計算すると展開式のうち主要項として残るのは  \frac{1}{2^{2N}}\times \sum _ {i=0}^t \sum _ {s=1}^{2^N-1}i\lambda _ s^{t-i}(h _ {0,s}-h _ {j,s}) の項となることが分かる。 \sum_{i=0}^t i\lambda _ s^{t-i} を評価すると大きい  t に対して  \frac{t}{1-\lambda _ s} が主要項として残ることが分かる。よって、分子の係数は (主要項とそれにつく係数以外を無視して)  \frac{1}{2^{2N}}\times t\times \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}(h _ {0,s}-h _ {j,s}) となる。分子と分母の評価を合わせて  x=1 での評価を行えば、結局求めたい値は  \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}(h _ {0,s}-h _ {j,s}) であることが分かる。

 

 答えの計算

 さて、この値を計算することを考える。各固有値  \lambda _ s の値は、与えられた確率の列を Hadamard 変換したものの第  s 要素そのものであり、高速 Hadamard 変換を用いて求められる。 v _ 0=0, v_s = \frac{1}{1-\lambda _ s}(s\neq 1) としてできるベクトル  v を考える。 \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}h _ {j,s} は、 v を Hadamard 変換したものの第  j 要素に他ならないため、これも高速 Hadamard 変換で求められる。最後に、 \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}h _ {0,s} は、上述の Hadamard 変換の第  0 要素である。このことから、この問題は、

・与えられた確率の列を高速 Hadamard 変換して各固有値を求め、

・上述の  v を計算し (ただの割り算)、

 v を高速 Hadamard 変換してできる列の第  0 要素から第  j 要素を引いた値を各  j に対して出力する

というアルゴリズムを用いて解くことができる。

 

 

ソースコード

 https://atcoder.jp/contests/agc034/submissions/5775887