POJいろいろ8/2

2441
http://poj.org/problem?id=2441

bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw

3254
http://poj.org/problem?id=3254

sampleも一発で通って気持ちがいい。bitdp。

3420
http://poj.org/problem?id=3420

行列累乗。一行ごとのstateをbitで表して行列を作る。16*16なので埋め込んでAC。ライブラリ化もしといた。

3171
http://poj.org/problem?id=3171

segtreeでdp高速化。[a, b)の区間を考えてやったのだから、当然updateすべきはb-1なのに、区間に含まれないbでupdateしていたのは良くない。

1274
http://poj.org/problem?id=1274

flowやるだけ。

2836
http://poj.org/problem?id=2836

前処理してbitdp。これも意外に思いつくのに時間がかかった。累積和も思いつかなかったし、前処理苦手?
何回も計算しているところ、無駄なところに注目すると前処理思いつきやすい?