ABC009 - D 漸化式

問題概要

• リンク:https://atcoder.jp/contests/abc009/tasks/abc009_4

問題文

整数列 $\{A_i\}$ が以下の漸化式で定められている:

$$A_{K+i}=(c_1\text{ and }A_{K+i-1})\text{ xor }(c_2\text{ and }A_{K+i-2})\dots\text{ xor }(c_K\text{ and }A_{i})(i>0)$$

$K,(A_1,A_2,\dots,A_K),(c_1,c_2,\dots,c_K),M$ が与えられるので、$A_M$ を求めよ。

制約

• 入力はすべて整数
• $1\leq K\leq100$
• $1\leq M\leq 10^9$
• 与えられる $\{A_i\}$ の先頭 $K$ 項は、すべて32bit符号なし整数に収まる。
• 与えられる $(c_1,c_2\dots,c_K)$ はすべて32bit符号なし整数に収まる。

解法

...結論は公式解説とあまり変わらないのだけれど、こちらの方が自然な発想な気がする。


まず、$\text{xor,and}$ の混じった計算はビットごとに分けると見通しがよくなったりする。
なぜならば、ビット演算はほかのビットには影響しない演算だから。足し算とかだと繰り上がりで影響してしまう!!!
今回は、$A_M$ を求める代わりに、$A_M$ の各ビットを求めてから $A_M$ を復元しよう。
以下、$A_M$は各ビットごとについて独立に考えているとする。
ビットごとに区切って見ても漸化式は変わらない。すなわち、$A,c$ を各ビットごとに見れば

$$A_{K+i}=(c_1\text{ and }A_{K+i-1})\text{ xor }(c_2\text{ and }A_{K+i-2})\dots\text{ xor }(c_K\text{ and }A_{i})(i>0)$$

が成り立つ。さらに、$A_i\in\{0,1\}$である(ビットごとに区切ったので)




ところで、$\bmod2$において

• $1\times1=1,1+1=0$
• $1\times0=0,1+0=1$
• $0\times1=0,0+1=1$
• $0\times0=0,0+0=0$

が成り立つのでした。...なんだかこれ、$\text{xor,and}$ に似てますね。実は$\{0,1\}$における$\text{xor,and}$ は $\bmod2$ における $+,\times$ に対応します。したがって、$\bmod2$ 上で以下が成り立ちます。

$$A_{K+i}=c_{1}A_{K+i-1}+c_{2}A_{K+i-2}\dots+c_{K}A_{i}=\sum_{j=1}^{K}{c_jA_{K+i-j}}(i>0)$$

ということで、$A$の漸化式を$\bmod2$における線形漸化式に帰着させることができた。
これを行列累乗を用いて計算することで、$O(wK^3\log M)$ で解くことができた。ただし、ここで$w$は$\log A_M$である。

TLEする

制限時間きつめなので、何かしらの定数倍高速化するほうがいいっぽい。

• mulでj,kを入れ替えると、メモリアクセスの関係でちょっと速くなる。
  • 高速化前
  • 高速化後

もうちょっとちゃんと考察すると、ビット並列にすることで計算量を $1/w$ にできる.