読者です 読者をやめる 読者になる 読者になる

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


分割統治

POJ 3233 Matrix Power Series

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

しょげないでよBaby 眠れば治る