分治FFT“自己卷自己”形/[CTSC2018]青蕈领主

众所周知分治FFT可以用来解决这样的问题

其中 \(G(x)\) 是一个已知的多项式
但是有的时候我们会遇到这样的情况，\(G(x)\) 的系数依赖与 \(F(x)\) 的 \(1\sim i-1\) 次项系数，这个时候直接分治FFT就不太行了
这里讨论的就是这种分治FFT“自己卷自己”形的一般性的处理方法
这里讨论的是

设 \(G(x)=F(x)\)显然另外的情况都可以表示成这个样子。

在这种情况下，不能直接运用之前的做法的一个原因是，在 \(f[l,mid]\) 向 \(f[mid+1,r]\) 转移的时候，实际上需要的 \(g[mid+1,r]\) 这一部分我们还没有。
考虑这个问题什么时候会出现，也就是 \(r-l\geq l\) 的时候。根据分治的过程我们不难发现这个等价于 \(l=1\)。
所以在 \(l>1\) 的时候我们应该是按之前的做就可以
但是 \(l=1\) 的时候因为不知道有半部分，所以只能 \([l,mid]\) 和 \([l,mid]\) 进行转移，在后面我们再把转移补偿回来。
所以这个时候再 \(l>1\) 的时候需要相应的进行改变
具体的流程是：

• \(l=1\)，直接 \([l,mid]\) 和 \([l,mid]\) 卷，累加到 \(f[mid+1,r]\) 上
• \(l\neq 1\)，先 \(f[l,mid]\) 和 \(g[l,r]\) 卷，累加到 \(f[mid+1,r]\) 上，再 \(g[l,mid]\) 和 \(f[l,r]\) 卷，累加到 \(f[mid+1,r]\)

这个不太好理解，我们可以想像对于 \([x+1,r]\)，他相当于是 \(f_i\) 和 \(g_j\) 转移过来的
那么有可能是 \(i,j\) 都在 \([l,x]\)，也有可能是 \(i\) 和 \(j\) 有一个在 \([x+1,r]\) 里。
上面两类可以理解为对应了两种转移。

下面是一道例题

P4566 [CTSC2018]青蕈领主

首先判断无解的情况，\(a_n\neq n\) 或者有两个区间相交
否则一定有解，为什么，猜。
对于每一个区间，他会直接包含一些区间，并且这些直接包含的区间并起来加上右端点就是这个区间
所以实际上可以表示成一个树形结构，每一个子树里的编号都是连续的
现在要求一个点的两个儿子之间不能是连续的，所以对于每一个点，可以把这个点和他们的儿子按照大小关系重新编号一下，相当于是求一个 \(L_i\) 是 \(1,1,1,\cdots x+1\) 的排列的个数（\(x\) 是儿子的个数）
考虑如何解决这个问题，事实上，直接解决是困难的。
但是我们注意到他的反排列 \(a_{-1}\) 满足 \(a^{-1}_{a_i}=i\)，如果 \(a_i\) 在 \([L,R]\) 上是连续的，那么 \(a^{-1}_i\) 一定在 \([\alpha,\beta]\) 上是连续的。
如果 \(a_i\) 的 \(L\) 是 \(1,1,1,1,x-1\) 的话，那么 \(a^{-1}\) 的长度大于1的连续区间只能有一个，并且必须包含这个区间的最大值。
并且反排列和原排列是一一对应的
我们现在用 \(f_i\) 表示长度为 \(i+1\)（注意长度） 的，连续区间长度大于1的连续区间包含区间最大值的排列的方案数
考虑从 \(i-1\) 到 \(i\) 的转移。

• 如果 \(i-1\) 构成的排列合法：
  我们考虑最大值除了在 \(i\) 两边的位置以外都可以插进去，所以有 \(i-1\) 种选法，转移量就是 \((i-1)f_{i-1}\)
• 如果 \(i-1\) 构成的排列不合法：
  事实上，这也代表着这个排列包含最大值的最长连续区间就是 \(1\) 和 \(i\)
  这个时候 \(i-1\) 构成的排列只有可能有一个不包含 \(i\) 的连续区间，现在我们要插入一个最大值 \(i+1\) 让他不合法。
  设这个连续的区间（值域）是 \([x,x+l-1]\)，注意到，对于 \(i+1\) 和 \([x,x+l-1]\)，把他们重新标号一下实际上就是 \(l+1\) 的长度的 \(f\) ，即 \(f_l\)。
  考虑 \(x,l\) 应当满足的条件，由 \(x+l-1 可知 \(l\leq i-2,x\) 有 \(i-l-1\) 种选法
  我们把 \([x,x+l-1]\) 看成一个点，继续和剩下的 \(i-l\) 个位置排序，这样转移量就是 \(f_{i-l}\)
  这样我们就得到了最终的转移

\(f_0=1,f_1=2\)
这个式子就和上面那个式子非常的像了，为了方便我们还可以把他改写一下

现在就是完全一样了

#include 

using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

const int N=1<<17;
const int mod=998244353;

typedef long long ll;
typedef double db;

# define chkmax(a,b) a=max(a,b)
# define chkmin(a,b) a=min(a,b)
# define PII pair
# define mkp make_pair

template void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int t,n;
int a[N];
int f[N],g[N];
int A[N],B[N];
int pos[N],tmp[N];
int stk[N],top;

int inc(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}

int dec(int x,int y){
    return x-y<0?x-y+mod:x-y;
}

int Qpow(int base,int ind){
    int res=1;
    while(ind){
        if(ind&1)res=1ll*res*base%mod;
        base=1ll*base*base%mod;
        ind>>=1;
    }
    return res;
}

void init(int limit){
    for(int i=1;i>1;
    solve(l,mid);
    if(l==1){
        int limit=1;
        while(limit<=2*mid)limit<<=1;
        Rep(i,1,mid)A[i]=f[i],B[i]=g[i];
        init(limit);
        kakeru(A,B,limit);
        Rep(i,mid+1,r)f[i]=inc(f[i],A[i]);
        for(int i=0;i=i-a[i])top--,x++;
            ans=1ll*ans*f[x]%mod;
            if(top&&stk[top]!=i-a[i]){flag=false;break;}
            stk[++top]=i;
        }
        if(!flag)puts("0");
        else printf("%d\n",ans);
    }
    return 0;
}