Matrix

SZKOpuł: Leonardo's Numbers

https://szkopul.edu.pl/problemset/problem/yGC3v6-xidN3ZW6QNlBAFZSU/site/?key=statementL(i+1)^x * L(i)^yを求める際に必要な情報を考えてみます。これを(x,y)と表記します。 L(i+1)^x = (L(i) + L(i - 1) + 1) ^ x = Σ(a+b+c L(i+1)^x * L(i)^y = Σ(a+b…

AOJ 2107: Can I go there?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107頂点を行列にするとうまく行かなくて、辺を行列にするといい。すなわち ある辺のうちどっちにいるかを値にして、次どこ行けるのか行列で持てば良い。 最初の1回はどこにもいけるので特別な辺…

POJいろいろ8/3

3109 http://poj.org/problem?id=3109座標圧縮+平面走査segtree。実装ややこしいはずだけど一発で通って気持ちがいい。実装ちゃんと練ればすんなりいくんだね。3735 http://poj.org/problem?id=37351+B+B^2...の形が出てくるので行列の累乗和を貼って終了、…

POJいろいろ8/2

2441 http://poj.org/problem?id=2441bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw3254 http://poj.org/problem?id=3254sampleも一発で通って気持ちがいい。bitdp。3420 http://poj.org/problem?id=3420行列累乗。一行ごとのstateをbitで表して行列…