https://www.luogu.com.cn/problem/P4721

$f_i = \sum f_{i - j} g_{j}$，边界是 $f_{0}=1$，$g$ 给出。

考虑设置一个 $B$，然后每次将 $f$ 扩展长度 $B$，然后块内可以用 $B^2$ 来处理。

复杂度为 $O(\frac{N}{B}(B^2 + N \log N))$。

实测和普通的分治 fft 差距并不大。

普通的分治 fft 类似 cdq 分治的方式，考虑得到一个区间 $[l, r]$。

  • 先递归左边，得到左边答案。
  • 假设左边得到的是正确的，计算给右边的贡献。
  • 然后递归右边。

$O(N\log^2 N)$:https://www.luogu.com.cn/record/33663228

$O(\frac{N}{B}(B^2 + N \log N))$:https://www.luogu.com.cn/record/123853754

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int BLOCK = 4000;
void solve() {
  int N;
  read(N);
  vi g(N);
  rep(i, 1, N) read(g[i]);
  vi F{1};
  while (sz(F) < N) {
    int len = sz(F);
    int len2 = sz(F) + BLOCK;
    cmin(len2, N);
    auto res = F * g;
    F.resize(len2, 0);
    rep (i, len, len2) {
      F[i] = res[i];
      rep (x, len, i) {
        F[i] += (ll)F[x] * g[i - x] % P;
        if (F[i] >= P) {
          F[i] -= P;
        }
      }
    }
  }
  rep (i, N) {
    cout << F[i] << " \n"[i + 1 == N];
  }
}

例题。

https://atcoder.jp/contests/abc315/tasks/abc315_h

code:https://atcoder.jp/contests/abc315/submissions/45261701