题解：P4721 【模板】分治 FFT

前置知识：FFT / NTT。

给定序列 $g_{1\dots n - 1}$ ，求序列 $f_{0\dots n - 1}$ 。
其中 $f_i=\sum_{j=1}^if_{i-j}g_j$ ，边界为 $f_0=1$ 。
答案对 $998244353$ 取模。

思路

观察题目，我们发现式子是一个卷积的形式。

但是

f

的每一项都是由前

O(n)

项递推来的。所以此时直接 FFT / NTT 会达到恐怖的

O(n^2 \log n)

（暴力是

O(n^2)

），所以

O(n \log n)

是行不通的。

那么，

O(n \log^2 n)

呢？

我们采用——分治！

对于一个我们要求的系数区间

[l, r]

（就是

f

的

l

次方项到

r

次方项的系数），具体是这样的：

先求出左半边 $[l, mid - 1]$ 的 $f$ 对自己的贡献，即只使用 $[l, mid - 1]$ 中的元素与 $g$ 相乘，且只需要答案的 $[l, mid - 1]$ 部分，我们发现这个可以递归。
求出左半边对右半边的贡献，即用 $[l, mid - 1]$ 中的元素乘 $g$ ，将乘积的 $[mid, r]$ 这几项加给 $f$ 的对应次方系数。
递归右半边。

我们发现操作中的

g

只有前

r - l + 1

项有用（后面的我们不需要），所以时间复杂度为递归乘 FFT / NTT 为

O(n \log^2 n)

。

注：最好补齐项数到

2

的次幂，这样每个递归区间长度都也是

2

的次幂，便于乘法。

Code

CPP

#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int maxn = (1 << 21) + 10, modd = 998244353, g1 = 3, gi = 332748118;

int n, G[maxn], F[maxn], rev[maxn];

int ksm(int a, int b) { // 快速幂
	int ress = 1;
	while (b) {
		if (b & 1) ress = ress * a % modd;
		a = a * a % modd;
		b >>= 1;
	}
	return ress;
}

void NTT(int *f, int len, int k) { // NTT 与模板毫无需要改动的地方（FFT 当然也可以）
	for (int i = 0; i < len; i++) {
		if (rev[i] > i) swap(f[i], f[rev[i]]); 
	}
	for (int d = 1, g, dg, nowa, nowb; d < len; d <<= 1) {
		dg = ksm((k == 1 ? g1 : gi), (modd - 1) / (d << 1));
		for (int i = 0; i < len; i += (d << 1)) {
			g = 1;
			for (int j = 0; j < d; j++) {
				nowa = f[i + j];
				nowb = g * f[i + j + d];
				f[i + j] = (nowa + nowb) % modd;
				f[i + j + d] = (nowa - nowb) % modd;
				g = g * dg % modd;
			}
		}
	}
	return ;
}

void solve(int l, int r) { // 核心代码
	if (l == r) { // 边界
		return ;
	}
	int mid = (r + l + 1) >> 1, nowl = (r - l + 1) << 1; // 这个 mid 把区间化成了 [l, mid - 1], [mid, r]
	solve(l, mid - 1); // 递归左边
	rev[0] = 0;
	rev[1] = (nowl >> 1);
	for (int i = 4, k = (nowl >> 2); i <= nowl; i <<= 1, k >>= 1) {
		for (int j = (i >> 1); j < i; j++) {
			rev[j] = rev[j - (i >> 1)] + k;
		}
	} // 这里 FFT / NTT 的长度会变化，所以需要动态维护 rev
	int nowf[nowl], nowg[nowl];
	for (int i = l; i < mid; i++) {
		nowf[i - l] = F[i];
	}
	for (int i = mid - l; i < nowl; i++) { // 注意不是全局变量的数组要赋初值
		nowf[i] = 0;
	}
	for (int i = 0; i <= r - l; i++) {
		nowg[i] = G[i];
	}
	for (int i = r - l + 1; i < nowl; i++) {
		nowg[i] = 0;
	}
	NTT(nowf, nowl, -1);
	NTT(nowg, nowl, -1);
	for (int i = 0; i < nowl; i++) {
		nowf[i] = (nowf[i] * nowg[i]) % modd;
	}
	NTT(nowf, nowl, 1);
	for (int i = 0; i < nowl; i++) {
		nowf[i] *= ksm(nowl, modd - 2);
		nowf[i] = (nowf[i] % modd + modd) % modd;
	}
	for (int i = mid; i <= r; i++) { // 加到右边
		F[i] += nowf[i - l];
		F[i] %= modd;
	}
	solve(mid, r); // 递归右边
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	n--;// 题面只需要求到 n - 1
	F[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> G[i];
	}
	int maxl = 1;
	while (maxl <= n) maxl <<= 1; // 补全成 2 的次幂
	solve(0, maxl - 1);
	
	cout << 1 << ' ';
	for (int i = 1; i <= n; i++) {
		cout << F[i] << ' ';
	}
	
	return 0; // 因为 long long, 我调了 4h
}

十年 OI 一场空，不开 long long 见祖宗。

题解：P4721 【模板】分治 FFT

文章操作

思路

Code

相关推荐

评论

题解：P4721 【模板】分治 FFT