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


行列

POJ 3233 Matrix Power Series

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

SRM 377 Div1 Medium GameOnAGraph

問題 無向グラフが与えられる。各頂点は白か黒の色で塗られており、辺は異なる色の頂点間でのみ張られている。このグラフ上で次の手順でゲームを行う。 白と黒が交互に行い、初手は白である。 白のターンでは各黒の頂点にその頂点と隣接する白の頂点の点数を…

Get up! 明日のSUPER ST@R!