問題概要 a[0]=1, b[0]=1である。a[n+1]=b[n], b[n+1]=a[n]+b[n]、ただし、いくつかのnについてはb[n+1]=a[n]/2である。a[K]+b[K]をmod 10^9+9(=:P)で求める問題。K 考えたこと (当時は行列計算実装している間に終わった記憶がある) 漸化式の形に落とすこと…

問題概要 長さL( 考えたこと (当時はシミュレーションをひーひー言いながら通した記憶がある。その後editorialで綺麗な解答に感心した) これは解き方覚えてる。偶奇のマスは干渉しないし、うさぎは2匹ずつ消えるので偶奇のマスにいるうさぎの数を数えて、そ…