プログラミングコンテストチャレンジブック 3-5 その2

第3章 3-5 の途中からです。

• 行列累乗
  • フィボナッチ数列 - フィボナッチ数列の n 項目の mod 1000 を求める問題
    • さらっとフィボナッチ数列の一般項が出てきてる。けど桁があふれるのでこのまま解くのは難しい
    • 漸化式を行列とベクトルの積で表現する → 行列の累乗を求めればよい
    • 行列の累乗も繰り返し二乗法を使って高速に計算できる
  • Blocks - ブロックの4色の塗り分けの場合の数(の mod)を計算
    • 同じように漸化式を立てて行列の累乗問題に落とせる
  • グラフの長さkのパスの総数
    • 名前の通りの問題。これも漸化式を立てて行列の累乗問題にする
  • Matrix Power Series
    • 今度は行列の累乗和というそのままの問題。ただし和を取らないといけない
    • [[A 0]; [I I]] という行列を導入することで、この行列の累乗を計算して A の累乗和が得られる
• データ構造を用いて高速化
  • Minimizing maximizer
    • n 個の数列から最大値を得る Maximizer という装置があって、これが部分列の sort を行なう部品のパイプラインとしてできている。あるMaximizer を与えられた時に正しく動作するように sorter の数を最小にする(いくつか取り除く)
    • 最大値が数列の最初にあった時に動作すれば常に正しく動く
    • 漸化式の更新する部分にセグメント木を利用すれば高速にできる

3-5 はこれで終わりです。3-6 はかなり長いですしまだ4章の上級編もあるので、本書はかなり先が長いですね。