POJ No. 3734 Blocks

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の6日目のエントリです．

せいかつに　よゆうがでてきて　きちんと　こうしんできるように　なった．

問題はこちら

蟻本で取り扱ってる問題．

問題要約

• パンダが1列に並んだブロックをペンキで塗る
• ブロックはN個で，ペンキは赤，青，緑，黄
• 赤と緑を偶数で塗りたい
• そのような組み合わせは何パターンあるか

解法

蟻本と一緒．
i番目で

• 赤・緑ともに偶数
• 赤・緑どちらかが奇数
• 赤・緑どちらも奇数

の場合に分けてパターン数を考えた時，i+1番目はどうなるかの関係式を作って行列で解く．
行列の式より，[latex]Aⁿ[/latex]をO(n)じゃなくてO(log n)で解く方法の方がネックになるんじゃないかと思った (頻出だけど)．
ソースコードのmatPowを参照．