畳み込みの和 [yukicoder No.754] - はまやんはまやんはまやん

考察過程

1. ★2の問題に見えないので、なるべく簡単に行けそうな道を探す
2. （NTTを知っていればそれを使いたくなるが、これは★2相当のアルゴリズムではない）
3. c[0]～c[N]をバラバラに求めよという問題ではないので、区別する必要が無いというところに計算量を落とす鍵がありそう
4. f(x)g(x)の計算なので、a[i]*b[j]の和を求めていくことになる
5. a[0]とかけて答えに含まれるのはb[0]～b[N]である
6. a[1]とかけて答えに含まれるのはb[0]～b[N-1]である
7. これを高速化すればできそう。これはbの和を更新していくことで解決可能

余談

この問題はNTTの入門として最適です！（ただしNTTは相当難しいアルゴリズムで★2の想定解ではない）

解法

https://yukicoder.me/submissions/303536

問題を言い換えると、
a[0]*(b[0]+...+b[N]) +
a[1]*(b[0]+...+b[N-1]) +
...
a[N]*b[0]
を求める問題。
bsm := 配列bの和
として、これを更新しながら、上記の式を計算していこう。
a[0]から順に見ていくが、bsm = b[0]+...+b[N]を計算していき、b[N],b[N-1]と順に引いていくことで
すべてO(1)で計算ができるので、全体の計算量O(N)で間に合う。

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N + 1) cin >> A[i];
    rep(i, 0, N + 1) cin >> B[i];

    mint ans = 0;
    mint bsm = 0;
    rep(i, 0, N + 1) bsm += B[i];
    rep(i, 0, N + 1) {
        ans += bsm * A[i];
        bsm -= B[N - i];
    }
    cout << ans << endl;
}