Contest5386 - NTT
Published:
A FFT/NTT快速傅立叶
首先要会 FFT。
注意到 $\bmod 998244353$ 意义下，$(3^{\frac {p-1} n})^k$ 和 $\omega_n^k$ 的性质非常相似，其中 $3$ 是 $998244353$ 的一个原根。（$998244353 - 1 = 2^{23} \times 7 \times 17$）
所以把所有单位根改成这个就好了。
void NTT(ll a[], int n) {
for (int i = 0; i < n; i++)
if (rev[i] > i)
swap(a[i], a[rev[i]]);
for (int len = 2, m = 1; len <= n; len <<= 1, m <<= 1) {
ll W = qpow(g, (MOD - 1) / len); // 最大的改动
for (int l = 0, r = len-1; r < n; l += len, r += len) {
ll w = 1;
for (int i = l; i < l + m; i++) {
auto x = a[i] + w * a[i + m], y = a[i] - w * a[i + m];
a[i] = x % MOD, a[i + m] = (y % MOD + MOD) % MOD;
w = w * W % MOD;
}
}
}
}
void INTT(ll a[], int n) {
NTT(a, n);
reverse(a+1, a+n);
ll invn = inv(n);
for (int i = 0; i < n; i++)
a[i] = a[i] * invn % MOD;
}
B 力
\[E_j = \left( \sum\limits_{i=1} q_i \times \frac 1 {(j-i)^2} \right) - \left( \sum\limits_{i=j+1}^n q_i \times \frac 1 {(i-j)^2} \right)\]左边的 $\sum$ 是一个卷积，FFT 秒了。
右边的 $\sum$ 是一个差卷积：
\[\begin{aligned} & \sum\limits_{i=j+1}^n q_i \times \frac 1 {(i-j)^2} \\ =& \sum\limits_{i=1}^{n-j} \hat{q}_i \times \frac 1 {(n-j+1 - i)^2} \end{aligned}\]其中 $\hat{q}$ 是 reverse 了的 $q$。
现在是卷积了，FFT 秒了。
整道题总共调用 $5$ 次 FFT 函数。