ABC#009 D.漸化式

教　育　的　問　題。
勉強になった。

問題

数列Aの初めのK項と漸化式、K項の数列Cが与えられる。

N>=1に対し、A_{N+K} = (C_1 AND A_{N+K-1}) XOR ... XOR (C_K AND A_N)
(AまたはCの値は符号なし32bit整数)

A_Mを求めよ。
1<=K<=100
1<=M<=10^9

考え方

a_{n+m}=(＋){b_i(×)a_{n+i}}形式の場合、漸化式の計算は「行列累乗」で高速に行うことできる。
x_M = (A_{N+M}, A_{N+M-1}, ..., A_{N+1})^Tとして、

x_M = F * x_{M-1}

になる。

行列Fは、場合によるが、今回の場合は、
C_1 C_2 ... C_K
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
...
のような感じ。

上記の行列の漸化式を繰り返すと、x_M = F^M * x_1みたいに最初のAのK項と行列の累乗になる。
行列の累乗は繰り返し二乗法(1,2,4,8,...乗を計算しておいて、F^Mを分解・前計算を利用して計算)で計算すればよい。

今回の場合は、*、+じゃなくて、AND、XORになっているので、行列Fの要素が1や0のところやかけ算の計算の部分が違うので注意。

繰り返し二乗法で、2進数で見てビットが立っているところを掛けていく方法以外にも、数が少なければ1/2したものを再帰的に書くのでもよいっぽい。

別解

http://d.hatena.ne.jp/wata_orz/20090922/1253615708
さらに高速に計算する方法に「きたまさ法」というのがあるらしい。

以下、勉強のため、wataさんのブログの書き写し。
漸化式が以下で書かれたとする。
a_m = Σ_{i=0}^{n-1} b_i * a_i + b_n * d
このとき、mを2mにすると、
a_{2m} = Σ_{i=0}^{n-1} b_i * a_{m+i} + b_n * d
a_{2m} = Σ_{i=0}^{n-1} b_i * {Σ_{j=0}^{n-1} b_j * a_{j+i} + b_n * d} + b_n * d
a_{2m} = Σ_{i=0}^{n-1} Σ_{j=0}^{n-1} {b_i * b_j * a_{j+i}} + (Σ_{i=0}^{n-1} b_i + 1) * b_n * d
で、必要なaはa_0からa_{2n-2}までになる。これが高速に計算できればよい。
さらに、ΣΣb_i * b_j * a_{j+i}はFFTでO(n log n)になる。