AtCoder Beginner Contest 009:D - 漸化式

問題

https://atcoder.jp/contests/abc009/tasks/abc009_4

考え方

難しい。半環上に定義される演算は行列の演算と同じことができる。フィボナッチ数列を行列で表すと以下のようになる。

{\displaystyle 
    \begin{pmatrix}
      1 & 1 \\
      1 & 0 \\
    \end{pmatrix}
    \begin{pmatrix}
      F_{k+1} \\
      F_{k} \\
    \end{pmatrix}
    = 
    \begin{pmatrix}
      F_{k+2} \\
      F_{k+1} \\
    \end{pmatrix}
}

これと同様の考え方でビット演算のANDとXORをANDは \times、XORは + に対応させることができる。単位元v = Long.MAX_VALUE として

{\displaystyle 
    \begin{pmatrix}
      v & 0 & 0 & \cdots \\
      0 & v & 0 & \cdots \\
      0 & 0 & v & \cdots \\
      0 & 0 & 0 & \cdots \\
      \cdots
    \end{pmatrix}
}

である。そのように考えると問題で与えられた操作は行列で定義できて、また第 M 項はフィボナッチ数列と同様の考え方で求めることができる。よって行列累乗で O(logM) で第 M 項を求めることができる。

どこに着目して考察するべきだったか

半環の演算に着目する。操作を行列で表すことで行列累乗が適応できる形になる。

何がバグっていたか

得た知見(典型ポイント)

  • 半環の演算に落とし込む

類題