脳log[20230704]

2023年07月04日 (火) [AtCoder] 精進。ABC009-D「漸化式」(黄 diff)。ABC を古い方から埋めていく取り組みでつまずいてつまずいたままになっている最初の問題。ベルトコンベア式に入力を出力へ変換していく装置がある。10^9 回の処理を繰り返すわけにはいかないのでどうやってプロセスを加速するか。どこかのツイートで行列累乗だと読んだんだよね。たしかに、それ以外にない見た目をしている(しかし気がつかない)。その人は FPS で解くシリーズをやっていたらしいけど。■提出 #43246893 (AC / 351 Byte / 1730 ms)。２回連続で行列の掛け算が書けなかったのがつい２週間前のこと(20230619)なので、今日は３度目の正直。■Ruby での提出一覧を見ると３桁 ms の提出がいくつもある。K^3logM を K^2logM にする Kitamasa 法というものがあるらしい。高速 Kitamasa 法というのは聞いたことがある気がするなあ。