Fibonacci Convolution Easy [yukicoder 978]

https://yukicoder.me/problems/no/978

解説

https://yukicoder.me/submissions/424701

数列自体は作成できるので、作成してしまおう。
答えを見てみると畳み込み計算をして総和みたいな感じになっている。
だが、畳み込み計算するには、制約が厳しいし、★も足りない。
なので、和をうまく使いながら計算していこう。

sm = a[1] + a[2] + ... + a[i]
ans = a[1]～a[i]での答え

これが既に計算されているとする。
この時a[i+1]を計算の考慮に加えたいときは、smは簡単。
sm += a[i + 1]とすれば、1～i+1の計算結果となる。
ansをa[1]～a[i+1]での答えにしたいのだが、差分を見てみると、
a[i+1]×a[1] + a[i+1]×a[2] + ... + a[i+1]×a[i+1]が足りないことが分かる。
これを変形すると、a[i+1]×(a[1] + a[2] + ... + a[i+1])となり、カッコはちょうど更新後のsmと等しくなる。
よって、ans += sm * a[i+1]で差分更新ができる。
これを繰り返して、ansが答え。

int N, p;
mint a[2010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> p;

    a[1] = 0;
    a[2] = 1;
    rep(i, 3, N + 1) a[i] = a[i - 1] * p + a[i - 2];

    mint sm = 0;
    mint ans = 0;
    rep(i, 1, N + 1) {
        sm += a[i];
        ans += sm * a[i];
    }
    cout << ans << endl;
}