>>915
なるほど
現在の状態に至る確率 (vector) と次の状態に遷移する確率 (現在の状態と独立な vector) の間の演算を畳み込みと見なすわけね
てっきり乗算とか剰余演算を高速化するって話かと思った

そう思うと別に言われてるほど悪問じゃないじゃん
O(nk^2) 解が通っちゃうのはダメだが