CodeChef May Challenge 2020 - Binary Land

• 問題
• AC

$1$が書いてあるマスから$1$が書いてあるマスへのパスの求め方だけ検討すればよい。

2地点間のパスの総数自体は単純なDPで求まる。DPの遷移は$N \times N$の行列で書けるので、行列積をセグメント木などに乗せれば${O}(N^3Q\log Q)$で解ける。また、クエリが単調なことを利用するとSWAGが使えて${O}(N^3Q)$になる。

満点を取るためにはもう少し頑張る必要がある。まず、遷移の行列が三重対角行列になっていることに注目すると、行列積は${O}(N^2)$になる。したがって、SWAGへのpushとpopはこの計算量でできる……が、三重対角行列同士の積が三重対角行列になるわけではないので、SWAGをfoldする時の掛け算はどうしても${O}(N^3)$になってしまう。しかし、pathクエリに対して必要なのは行列そのものではなく一点の値なので、そこだけ求めるのは${O}(N)$で可能だった。これで${O}(N^2Q)$になった。

これでもなかなかACできなかった。行列をなるべく陽に持たずに省略できる部分は省略して、定数倍高速化を徹底するとようやく通った。