0. 前言

你需要知道：

  • FFT 或 NTT。
  • CDQ 分治。

1. 介绍

分治 FFT，用于解决这一个问题：

给定长为n−1n-1 的序列gg，求长为n−1n-1 的序列ff，满足：
fi=∑j=1ifi−jgjf_i=\sum_{j=1}^i f_{i-j}g_j，边界为f0=1f_0=1。
要求时间复杂度O(nlog⁡2n)O(n\log^2 n)。

你可能会说：“这不就是卷积吗，FFT秒了！”但是你发现这玩意不太对劲，因为你卷积默认你是知道ff，现在问题在于你不知道ff，要一个一个求。

我们解决这个问题可以利用 CDQ 分治的思想，具体的，设 solve(l,r) 表示计算g[l,r]g[l,r] 内这一段子问题的函数，注意这里算的不是fif_i，而是这一段自己对自己的贡献。为了我们 FFT 的方便，一开始肯定是调用 solve(0,1<<k) 的形式。

让后就是分治的部分，首先midmid 劈成[l,mid],[mid,r)[l,mid],[mid,r) 两段，令len=r−llen=r-l。左边一段我们可与i递归往下计算，但是对于右边我们需要计算左边对右边的贡献，因为i−ji-j 可能跑到[l,mid][l,mid] 里面。计算左侧ff 的贡献，可以发现对右半边位置xx 的贡献为：

∑i=lmidfi×gx−i\sum_{i=l}^{mid} f_i \times g_{x-i}

故可以卷积快速计算，时间复杂度O(nlog⁡2n)O(n \log^2 n)。

以下为模板题代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e7+15;
int f[MN],g[MN],ans[MN],len,n,m;

namespace BJXPoly{
    constexpr int MOD=998244353,G=3,INVG=332748118;
    int rev[MN],tmp[MN],ta[MN],tb[MN];

    int ksm(int a,int b){
        int ret=1;
        while(b){
            if(b&1) ret=ret*a%MOD;
            a=a*a%MOD;
            b>>=1;
        }
        return ret;
    }

    void dorev(int f[],int len){
        for(int i=0;i<len;i++){
            rev[i]=rev[i>>1]>>1;
            if(i&1){
                rev[i]|=len>>1;
            }
        }
        for(int i=0;i<len;i++){
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
    }

    void NTT(int f[],int len,int op){
        dorev(f,len);
        for(int i=1;i<len;i<<=1){
            int Wn=ksm((op==1?G:INVG),(MOD-1)/(i<<1));
            for(int j=0;j<len;j+=(i<<1)){
                int w=1;
                for(int k=0;k<i;k++,w=(w*Wn)%MOD){
                    int x=f[j+k],y=w*f[j+k+i]%MOD;
                    f[j+k]=(x+y)%MOD;
                    f[j+k+i]=(x-y+MOD)%MOD;
                }
            }
        }
        if(op==-1){
            int invlen=ksm(len,MOD-2);
            for(int i=0;i<len;i++) f[i]=f[i]*invlen%MOD;
        }
    }

void Mul(int a[], int b[], int n, int m){
    // 注意一定要复制一份再去做 NTT，不能覆盖原数组
    int len=1;
    while(len < n+m-1) len <<= 1;
    static int ta[MN], tb[MN];
    for(int i=0;i<len;i++) ta[i] = (i<n ? a[i] : 0);
    for(int i=0;i<len;i++) tb[i] = (i<m ? b[i] : 0);
    NTT(ta, len, 1);
    NTT(tb, len, 1);
    for(int i=0;i<len;i++) ta[i] = ta[i] * tb[i] % MOD;
    NTT(ta, len, -1);
    for(int i=0;i<len;i++) a[i] = ta[i]; 
}


    void cdq(int l,int r){
        if(l+1==r) return;
        int mid=(l+r)>>1;
        int len=r-l;
        cdq(l,mid);
        for(int i=0;i<len*2;i++){
            tmp[i]=0;
        }
        for(int i=l;i<mid;i++) tmp[i-l]=f[i];
        Mul(tmp,g,len*2,len*2);
        for(int i=mid;i<r;i++) (f[i]+=tmp[i-l])%=MOD;
        cdq(mid,r);
    }

}

signed main(){
    read(n);
    for(int i=1;i<n;i++){
        read(g[i]);
    }
    int lim=n;
    while(lim!=(1<<__lg(lim))) ++lim;
    f[0]=1;
    BJXPoly::cdq(0,lim);
    for(int i=0;i<n;i++){
        put(f[i],0);
    }
    return 0;
}

2. 升级分治 FFT

我们思考，分治 FFT 的过程依赖于 CDQ 来计算贡献。回顾整个过程，它总是按照下标的顺序来一次一次计算出答案。

既然我们要升级，借助这个 CDQ 分治的结构树，我们思考，假设我们询问位置的值的时候，允许对值进行一些修改？

那么稍加分析，发现如果我们进行了修改，修改是有效的，因为我们 CDQ 在分治计算贡献的时候显然会把这个贡献在回溯分治树的时候依次计算到后面，大区间的贡献就包含了我们修改后的贡献。并且发现复杂度是正确的O(log2n)O(log^2 n)。

也就是说，CDQ 递归的任意层，修改当前层左半区间的ff 值，是有效且可行的，这样该层的卷积贡献会重新计算（局部 FFT），然后这个修改会继续往更上层递归传播，沿着递归树路径逐层更新。

更进一步！我们尝试把gg 也给修改！

发现不行，因为gg 的贡献一个一个改的话是让整个递归树贡献受到影响时间复杂度O(n)O(n) 了。

不过还好，我们发现分治 FFT 可以通过小范围的修改来支持添加删除贡献的的操作，这个操作相当于将分治 FFT 进一步的升级了，恭喜你，你的分治 FFT 升级为了：半在线卷积。

半在线卷积的半在线是什么意思呢？回看我们的 CDQ 分治过程，前半段结果在递推时即时产生，后半段则依赖前半段，用分治+FFT一次性批量算出。所以叫“半在线”，是因为它的依赖关系是在线的（必须先知道前面的ff 才能算后面的），但计算方式是批量的（一次 FFT 更新一大段），不像纯在线卷积那样每步只更新一个元素。

不叫在线，是因为fif_i 仍然是按顺序被解锁的，在计算fmidf_{mid} 之前，f<midf_{<mid} 已经全部算出来，可以被使用；但右半段的贡献是一次性批量算的，不是每次求一个fif_i 就更新一次卷积结果，所以它不是完全在线的。

有一道 DP 例题，供大家练练手：CF553E。

3. 例题

CF553E

考虑倒着 DP，设f(i,j)f(i,j) 表示第ii 个点走到nn，当前时间为jj 的期望。有转移：

f(u,j)=min⁡v∈son(i){∑kf(v,j+k)⋅pu,k}+wif(u,j)=\min_{v\in son(i)} \{ \sum_{k} f(v,j+k)\cdot p_{u,k} \}+w_i

末状态f(u,i)=dis(u,n)+x,i>tf(u,i)=dis(u,n)+x,i>t，f(n,i)=0,i≤tf(n,i)=0,i\le t

时间复杂度O(nt2)O(nt^2)，无法通过，考虑优化，发现一堆优化板子都套不上去，但是发现 FFT 可以套上去。考虑 FFT 优化，但是注意到这个玩意差卷积不能卷因为这玩意是半在线的。考虑分治 FFT，但是对什么进行分治呢？考虑分析转移方程，注意到方程中时间的转移时具有顺序的，可以进行 CDQ。不妨对时间一维分治。

具体的，记g(u,v),jg_{(u,v),j} 来表示∑k=1tp(u,v),k×f(v,j+k)\sum_{k=1}^t p_{(u,v),k} \times f(v,j+k)，用f→gf \to g，在分治底层计算出f(u,j)=min⁡v∈son(i){∑kf(v,j+k)⋅pu,k}+wif(u,j)=\min_{v\in son(i)} \{ \sum_{k} f(v,j+k)\cdot p_{u,k} \}+w_i，时间复杂度O(mtlog⁡2t)O(mt\log^2 t)。

好消息是又学会了一个科技。

反思：DP 优化不仅仅可以从状态优化和一类特殊的转移优化，也可以通过转移的顺序进行优化。