分治 FFT

LuoguP4721

考虑分治

$$f_i=\sum\sum_{j=l}^{mid}f_i\times g_{i-j}$$

防止 $l$ 前的元素的干扰,截取有效部分做卷积。

时间复杂度 $\Theta (nlog^2n)$

void solve(int l, int r) {
  if (l == r) 
    return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  for (int i = 0; i <= r - l; i++)
    A[i] = B[i] = 0; 
  for (int i = 0; i <= mid - l; ++i)
    A[i] = f[i + l];
  for (int i = 0; i <= r - l; ++i)
    B[i] = g[i];
  DFT(A, r - l + 1), DFT(B, r - l + 1);
  for (int i = 0; i <= r - l; ++i)
    A[i] = (ll)A[i] * B[i] % mod;
  IDFT(A, r - l + 1);
  for (int i = mid + 1; i <= r; ++i)
    f[i] = (f[i] + A[i - l]) % mod; 
  solve(mid + 1, r);
}
最后修改:2020 年 05 月 03 日 09 : 15 PM
如果觉得我的文章对你有用,请随意赞赏