📚

ABC009 - D 漸化式

2023/04/10に公開

問題概要

問題文

整数列 \{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する

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

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

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

Discussion

ログインするとコメントできます