思路
设 $g_i = \sum_{j + k = i} f_j f_k$,那么 $f_i = a_i \sum_{j < i} g_j$。
如果 $f,g$ 互推,则有一个 $O(n^2)$ 的算法。
考虑分治 FFT,如果要求的是 $g_7$,如下图:
将 $g_7$ 的之分解为四类,即 $[0,3]$,$[4,5]$,$[6, 6]$,$[7, 7]$ 对其的贡献,也就是所有左边对右边的贡献。
若当前递归到的区间为 $[l,r]$,则做三个操作:
- 递归 $[l,mid]$
- 计算 $[l,mid]$ 对 $[mid + 1, r]$ 的贡献
- 递归 $[mid + 1, r]$
仔细思考一下,发现当 $l = 0$ 时,计算左对右的贡献时,会有一部分 $f$ 还没有计算出,而那一段就是除了 $l = 0$ 的区间以外的区间,所以计算贡献时,若 $l > 0$ 则有一个为 $2$ 的常数。
代码
感觉代码更好理解。
#include <bits/stdc++.h>
#include "atcoder/convolution"
using namespace std;
using atcoder::convolution;
using mint = atcoder::modint998244353;
const int N = 1200010;
const double PI = acos(-1);
int n, t[N];
mint f[N], g[N];
void solve(int l, int r) {
if (l == r) {
if (!l) return;
return f[l] = g[l - 1] * t[l], g[l] = g[l] + g[l - 1] + 2 * f[l], void();
}
int mid = l + r >> 1;
solve(l, mid);
auto T = convolution(vector<mint>(f + l, f + mid + 1), vector<mint>(f, f + r - l + 1));
for (int i = mid + 1; i <= r; i ++ ) g[i] = g[i] + T[i - l] * ((l > 0) ? 2 : 1);
solve(mid + 1, r);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &t[i]);
f[0] = 1; g[0] = 1;
solve(0, n);
for (int i = 1; i <= n; i ++ ) printf("%d ", f[i].val());
return 0;
}