cdqNTT

分治NTT

引出问题：

$$给定序列g_1,g_2,g_3...g_{n-1},现有序列f满足f_i=\sum_{j=1}^{i}f_{i-j}g_j,且f_0=1，求序列f_0,f_1,f_2,f_3....f_n-1 \\ 答案模998244353$$

看到这个递推式，第一眼一定是暴力，但是我们会发现，暴力的时间复杂度为$O(n^2)$，显而易见时间复杂度太高

那么这个时候，我们不妨考虑CDQ分治

$$我们考虑序列区间[left,right]中[left,mid]对区间[mid+1,right]的影响\\ 显而易见，对于x\in[left,mid]而言，它对y\in[mid+1,right]贡献为：\\ f_x\times g_{y-x}\\ \therefore f_y=f_y+\sum_{i=left}^{mid}f_ig_{y-i}$$

所以我们可以通过NTT将卷积的部分给计算出来，然后将相应的部分加上去便可以得到最后的答案。

计算一下时间复杂度：

由于我们是分治再套上NTT求卷积因此，时间复杂度为：$O(nlog^2n)$

分治NTT模版

Poly f,g;//封装的多项式
// CDQ分治，先求出f[l,mid)​，可以发现这部分对区间的f[mid,r)​的贡献是f[l,mid)∗g[0,r−l)
void cdqntt(int l, int r)
{
    if (l == r)
    {
        、、、、、、、
        return;
    }
    int mid = (l + r) >> 1;
    cdqntt(l, mid);
    f.a.clear(), g.a.clear();
    for (int i = l; i <= mid; i++)
    {
        f.a.push_back(F[i]);
    }
    for (int i = 0; i <= r - l; i++)
    {
        if (i == 0)
        {
            g.a.push_back(0);
        }
        else
        {
            g.a.push_back(G[i]);
        }
    }
    Poly fA = (Poly)f * g;//多项式NTT计算
    for (int i = mid + 1; i <= r; i++)
    {
        //计算贡献
    }
    cdqntt(mid + 1, r);
}