解いた問題のソースコードと解説など。


分割統治

POJ 3790 Recursively Palindromic Partitions

問題 与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。回文となるような分割をPalindromic Partitionという。そのうち以下の条件を満たす分割をRecursively Palindromic Partitionsという。 条件:分割の左右それぞれ…

POJ 3233 Matrix Power Series

問題 nxnの行列Aが与えられる。S=A+A^2+A^3+...+A^kを計算し、各要素をmで割ったあまりを求めよ。 やりかた 行列の累乗は繰り返し二乗でできるとしても単純にやったら確実にTLEする。なのでうまく分割統治しつつメモ化しておくことで通すことができる。数列…

罪を憎んで人は憎まずにセクシー