ABC199 F - Graph Smoothing (600)
解説の方法
$ k \le 10^9と大きいのでK回分を愚直に試す方法は全て間に合わない
1回の操作を行列で表す
詳しくは解説を
$ N回目の期待値を$ N-1回目の期待値の式で表すと求められそう
行列を求めたらそれを$ k乗する
行列の更新をin-placeでやると、更新前後の値が混ざって壊れるので注意
行列の更新がボトルネックで、一回の更新が$ \mathcal{O}(N^3)、回数が$ \log k回なので全体で$ \mathcal{O}(N^3 \log K)