ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC009 D - 漸化式

リベンジ 半環 行列 バイナリ法

D - 漸化式
提出コード
かなり難しいです。ほぼ数学です。
漸化式をうまく行列に落とし込んで表現する方法を考えます。
まず、前提条件として非負整数はXORとANDに関して半環をなす、ということを理解している必要があります。
XORを足し算、ANDを掛け算のようにして行列の計算ができる、ということだけわかればいいです。そして、問題ので与えられた漸化式を行列で表現すると次のようになります。

{\displaystyle 
  \begin{pmatrix} 
A_{N+K+1}\\
A_{N+K}\\
\vdots \\
A_{N+3} \\
A_{N+2}
\end{pmatrix}
=
    \begin{pmatrix}
      C_1 & C_2  &\cdots&C_{K-1} &C_K \\
      1 & 0 &\cdots&0 &0\\
0 & 1  &\cdots &0 &0\\
\vdots&\vdots &\ddots& \vdots&\vdots\\
0&0& \cdots &1 &0
    \end{pmatrix}
  \begin{pmatrix} 
A_{N+K}\\
A_{N+K-1}\\
\vdots \\
A_{N+2} \\
A_{N+1}
\end{pmatrix}
}


そして、M番目の答えを求めるためには、

{\displaystyle 
    \begin{pmatrix}
      C_1 & C_2  &\cdots&C_{K-1} &C_K \\
      1 & 0 &\cdots&0 &0\\
0 & 1  &\cdots &0 &0\\
\vdots&\vdots &\ddots& \vdots&\vdots\\
0&0& \cdots &1 &0
    \end{pmatrix}
}

この行列を(M-K)回かけることを繰り返し、一番上にあるものを参照すればよいことになります。掛け算はandで、足し算はxorで行うことや、ここでの1は、ただの1ではなく、ビットをすべて立てている、という意味の1になる点に注意してください。2^{x}-1ということです。

愚直にかけると間に合わないので、2乗、4乗、8乗…2^{i}乗を求めておき、必要なものを随時かけていく、というようにすれば間に合います。バイナリ法と言うらしいです。