📚
ABC009 - D 漸化式
問題概要
問題文
整数列
が以下の漸化式で定められている: \{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\} 項は、すべて32bit符号なし整数に収まる。K - 与えられる
はすべて32bit符号なし整数に収まる。(c_1,c_2\dots,c_K)
解法
...結論は公式解説とあまり変わらないのだけれど、こちらの方が自然な発想な気がする。
まず、
なぜならば、ビット演算はほかのビットには影響しない演算だから。足し算とかだと繰り上がりで影響してしまう!!!
今回は、
以下、
ビットごとに区切って見ても漸化式は変わらない。すなわち、
が成り立つ。さらに、
ところで、
1\times1=1,1+1=0 1\times0=0,1+0=1 0\times1=0,0+1=1 0\times0=0,0+0=0
が成り立つのでした。...なんだかこれ、
ということで、
これを行列累乗を用いて計算することで、
Discussion