ABC009 D問題 漸化式

abc009.contest.atcoder.jp

 半環問題ってやつらしい。半環は前に調べたので今回は方針だけ。

基本方針

 漸化式を行列による計算と見なせば、二進累乗を使うことができるので、計算回数をlogD回に圧縮できる。K次正方行列同士の積はK^3、K次正方行列と列ベクトルの積はK^2で計算できる。全体の計算量はO(K^3logD)。

具体的な方針

 XORを加法、ANDを乗法と見なすと、行列の積における加法・乗法をそのように定義しても半環をなす。なので、普通の行列と同じように計算することができる。ちなみにこの時、加法単位元は0だけど乗法単位元は0xFFFF…であることに注意。地味にハマった。

実装

abc009.contest.atcoder.jp

感想

 初見だと「なんだこの問題!」って気持ちは出てくる(出てきた)けど、アルゴリズムとしてすごく考えられてる感じがして、ものすごく好きな問題。あるいは単純に二進数が好きなだけかもしれないけど。

 ちなみに半環問題っていう名前はここで知った。これもそのうち解きたい。