AtCoder Beginner Contest 009 D. 漸化式
解法
線形漸化式は行列の累乗を用いて解ける(プログラミングコンテストチャレンジブック pp.180-185)。
ただし今回は×がandに、+がxorになっている。
しかしこれは、行列累乗の際の計算で、×, +をand, xorにそれぞれ置き換えて計算すれば良い。
実際には、2つの二項演算(和と積)を備えた集合が、半環であればよい。(半環の性質は解説p.92に載っている)
http://www.slideshare.net/chokudai/abc009/92
この性質を実際に確かめる(1bitごとに全ての場合を計算すればよい)と、
xor: 結合法則、交換法則、単位元(0)を持つ
and: 結合法則、単位元(全てのbitが1、ここでは(1<<32)-1)を持つ
andとxorで分配法則が成立
xorの単位元(0)はandの零元
が全て成立するので、and, xorは非負整数の集合で半環をなす。
後は計算するだけ。
計算量
O(K^3 log M)
コード
解法2
上記のコードをジャッジに投げるとTLEする。
(2017年5月2日注釈: 現在はAtCoderの選択言語にPyPy2, PyPy3が追加されており、これらを使えば上記解法でもACは可能になった)
なのでここでは、M項目をO(K^2 log M)で求めることができる(いわゆる)きたまさ法を用いればよい。
コード
きたまさ法については、Spaghetti Source(github版の方)をお借りした。
(きたまさ法の説明についても、Spaghetti Sourceにあるコメントは簡潔で分かりやすいと思う)
GitHub - spaghetti-source/algorithm: C++ Implementation of Algorithms (aka. Spaghetti Source)
感想
線形漸化式で解ける式の形(?)を、半環という一般的なところまで落とし込めていなかったので、勉強になった。
O(KlogKlogM)で解く高速きたまさ法というのもあるらしい。(c[i+j] += c[i] * c[j]の計算は畳込みだから、FFTを用いて高速に計算できる、ということを用いる)
