DP高速化:ダブリング
競プロ典型90問
AtCoder
競プロ典型90問とその類題
競プロ典型90問難易度7
漸化式
DP
行列
行列累乗
ダブリング
整数を「10倍してaを足す」で捉える
DP状態:あまり
sparseな問題
DP高速化:FFT
FFT
DP高速化:きたまさ法・Bostan-Mori法
数え上げ問題
DP高速化:ダブリング
DP状態:どの桁まで見たか(広義の桁DP)
きたまさ法によく似たタイプの DP ダブリング高速化! ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意!!! 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …