ABC469 G - K-nacci Operations

[river0525]

問題の感想や気づきを投稿・共有するスペースです

[Maruoka842]

アフィン変換a_ix+b_iと置くと、a_{i+1}=a_{i-K}、b_{i+1}=(a_i+1)b_i-a_{i-K}b_{i-K}。a_i=-1 があれば遷移は下三角で、特性多項式は (x+1)^d(x-1)^{K+1-d}。なければ定係数漸化式。