首先观察到这个形式，容易发现它和常规的卷积不同点就在于：题目给出的求和定义中，\(\sum\) 符号下面的式子是 \(i+j<N\) 求和而不是 \(i+j=N\)。
为了方便计算，我们引入：
\[G_n=\sum_{i+j<N}F_iF_j \]我们发现，假设所有 \(F_{1\sim{i-1}}\) 已经求解完毕了，那么我们就可以通过之前的量算出 \(G_i\)，再转而去乘上 \(A_n\) 得到 \(F_i\)。
模拟题意的过程是 \(O(N^3)\)，而利用 \(F,G\) 相互递推这个做法是 \(O(N^2)\) 的。这都没法满足数据范围需要的时间要求。
这时候，我们根绝由小推大的性质想到了利用 \(\text{CDQ}\) 分治去优化这个 \(O(N^2)\) 的算法。具体的，就是分治 \(\text{NTT}\)。为了更好地理清这个问题，我们不妨再来看一下 \(\text{CDQ}\) 分治的模板框架：
-
当前区间长度为 \(1\)
直接进行一些特殊的处理。
-
当前区间 \([l,r]\) 长度 \(>1\)
- 递归处理左边区间 \([l,mid]\)
- 计算左边区间对右边的贡献
- 递归处理右边区间 \([mid+1,r]\)。
我们在长度为 \(1\) 的情况下就按照暴力中的处理方式来做，长度大于 \(1\) 就先递归做区间，中间利用 \(\text{NTT}\) 卷一下处理对右边的贡献，最后递归右边就行了。
值得一提的是，中间卷积处理贡献时，我们要分别计算 \(i\in[l,mid]\) 时的贡献，\(j\in[l,mid]\) 时的贡献（根据题意，如果两者都满足自然也是要算两遍），且 \(l=0\) 时特殊处理一下即可。
点击查看代码
#include <bits/stdc++.h>
#include "atcoder/convolution"
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
using atcoder::convolution;
using mint = atcoder::modint998244353;
constexpr int N = 2e5 + 10;
int n, A[N]; mint F[N], G[N];
void Solve(int l, int r){
if(l == r){
if(l) F[l] = (G[l] = G[l - 1] + F[l]) * A[l];
return;
}
int mid = l + r >> 1; Solve(l, mid);
if(!l){
auto T = convolution(vector<mint>(F, F + mid + 1), vector<mint>(F, F + mid + 1));
FL(i, mid + 1, r) F[i] += T[i - 1];
}
else{
auto T = convolution(vector<mint>(F + l, F + mid + 1), vector<mint>(F, F + r - l + 1));
FL(i, mid + 1, r) F[i] += T[i - l - 1] * 2;
}
Solve(mid + 1, r);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n; FL(i, 1, n) cin >> A[i];
F[0] = 1, Solve(0, n);
FL(i, 1, n) cout << F[i].val() << " \n"[i == n];
return 0;
}