LOJ 2554 「CTSC2018」青蕈领主——结论（思路）+分治FFT

一个“连续”的区间必然是一个排列。所有 r 不同的、len 最长的“连续”区间只有包含、相离，不会相交，不然整个是一个“连续”区间。

只有包含、相离，可以看出一个树形结构。直接暴露在自己区间里的小区间（即没有被其他小区间包含）就是自己的孩子。

每个孩子的值是一个区间，自己的值也是一个区间，不同孩子的区间不能融合，所以每个孩子看成一个点，自己的右端点也是一个点，值就是一个长度为 “孩子个数+1” 的合法排列。合法指的是除了最后一个位置的 len 是区间长度，其他位置的 len 都是 1 。

令 f[ i ] 表示长度为 ( i+1 ) 的合法方案。答案就是 \( \prod\limits_{i} f[ ct[i] ] \) ，其中 ct[ i ] 表示 i 区间的孩子个数。

有一个关于 f[ i ] 的递推式： \( f[1]=2, f[n]=(n-1)f[n-1]+\sum\limits_{i=2}^{n-2}(i-1)f[i]f[n-i] \)

那么可以分治 FFT 来求 f[ ] 。

关于证明，洛谷题解的第一篇（2019.1.17那一篇）说得很好：https://www.luogu.org/problemnew/solution/P4566

以下就是上面题解的复述：

考虑从 f[ n-1 ] 转移到 f[ n ] ，即从长度为 n 的排列转移到长度为 n+1 的排列。

先转换一下。“连续”区间只能是包含最后一个位置的。把 “值” 和 “位置” 反一下，“连续”区间只能是包含最大值的。

1.原来就是合法的。那么把原来的值改成 [ 2 , n+1 ] ，再把 1 找一个位置插入。长为 n ，有 (n+1) 个位置可以插入，但不能插入在 2 的两侧，所以就是 (n-1) 个位置。

　　这样插入之后，序列还是合法的。不然，不合法序列的值一定是 [ 1, x ] ，那么把 1 拿走，原来（+1之前）的值就是 [ 1 , x-1 ] ，即原来就是不合法的。

2.原来是不合法的。

　　考虑加入 1 之后变成合法的。只能有 1 个 “没有经过最大值的连续区间” ，再多的话就无法通过插入一个数来使序列变合法。

　　设这个区间的长度是 L 。

　　(1)它的值是连续的。

　　　　考虑取值，设为 [ x , x+L-1 ] （所有值是 [ 2 , n+1 ]）。它不经过最大值，所以 x+L-1 <= n ；它不能含有 2 ，否则加入 1 之后还是连续的，所以 x>2 ，解得 2 < x <= n-L+1 ，所以它的取值有 ( n-L-1 ) 种。

　　(2)插入一个 1 之后，它就是合法的。

　　　　这个 1 不会和区间里的任意一个值相邻。所以这个 1 两边的部分可以是 “连续” 的，然后用 1 隔开。

　　　　也就是说，这个 1 可以被原来的 “连续” 区间随便经过。考虑到 f[ ] 表示的是最大值可以被 “连续” 区间随便经过，所以不妨认为 1 就是这个区间里的最大值。

　　　　这样，这个区间可以视作长度为 L+1 的排列。合法方案是 f[ L ] 。f[ L ] 里包含的方案，不经过 1 的部分一定不 “连续” ，经过 1 的部分可以 “连续” ，刚好符合。

　　(3)整个序列只有一个 “没有经过最大值的区间” 。

　　　　刚才那个长度为 L 的区间确定好方案，可以缩成一个点。其他位置和该点一共 ( n-L+1 ) 个点。使用 f[ n-L ] 即可。

　　　　f[ n-L ] 里包含的方案，就是不看刚才那个长度为 L 的区间的话，没有其他不合法的 “连续” 区间。

　　　　刚才那个插入了 1 以后的区间，在 n-L+1 个点里的取值，可以看做是去掉 1 的最小值的排名，即 [ x , x+L-1 ] 这个值域在整个 [ 2 , n+1 ] 里的排名。

　　　　去掉 1 来看不会有问题。因为如果 1 有影响使得在 f[ n-L ] 里的方案因为有了 1 而不合法，用类似 “1.” 里的方法可以证明。

　　(4) L 的长度范围是 [ 2 , n-2 ] 。

　　　　 L 不能是 1 ，不然该区间合法。 x 的取值是 2 < x <= n-L+1 ，需要 n-L+1 > 2 ，所以 L < n-1 。这是在说 L 如果太长，就不能满足 “不过最大值” 又 “不含 2 ” 了。

自己的分治 FFT 似乎总是较慢。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=5e4+,M=(<<)+,mod=;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

int n,f[N],g[N],len,a[M],b[M],r[M],inv[M],wn[M],wn2[M];

struct Node{

  int l,r;

  Node(int l=,int r=):l(l),r(r) {}

}sta[N];

void init()

{

  for(len=;len<(n<<);len<<=);

  for(int R=;R<=len;R<<=)

    {

      inv[R]=pw(R,mod-);

      wn[R]=pw(,(mod-)/R);

      wn2[R]=pw(,(mod-)-(mod-)/R);

    }

}

void ntt(int *a,bool fx)

{

  for(int i=;i<len;i++)

    if(i<r[i])swap(a[i],a[r[i]]);

  for(int R=;R<=len;R<<=)

    {

      int Wn=fx?wn2[R]:wn[R];

      for(int i=,m=R>>;i<len;i+=R)

    for(int j=,w=;j<m;j++,w=(ll)w*Wn%mod)

      {

        int x=a[i+j], y=(ll)w*a[i+m+j]%mod;

        a[i+j]=upt(x+y); a[i+m+j]=upt(x-y);

      }

    }

  if(!fx)return; int iv=inv[len];

  for(int i=;i<len;i++)a[i]=(ll)a[i]*iv%mod;

}

void solve(int L,int R)

{

  if(L==R)

    {

      if(L==)f[L]=;

      else

    {

      f[L]=(f[L]+(ll)(L-)*f[L-])%mod;

      f[L]=upt(f[L]-(ll)(L-)*f[]%mod*f[L-]%mod);

    }

      g[L]=(ll)(L-)*f[L]%mod; return;

    }

  int mid=L+R>>; solve(L,mid);

  int d2=R-L+,d=mid-L+;

  for(len=;len<d+d2;len<<=);

  for(int i=,j=len>>;i<len;i++)

    r[i]=(r[i>>]>>)+((i&)?j:);

  int i,j;

  for(i=,j=L;j<=mid;i++,j++)a[i]=f[j]; for(;i<len;i++)a[i]=;

  for(i=,j=L;j<=R;i++,j++)b[i]=g[i+]; for(;i<len;i++)b[i]=;

  ntt(a,); ntt(b,);

  for(i=;i<len;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,);

  for(i=mid+,j=i-L-;i<=R;i++,j++)f[i]=upt(f[i]+a[j]);

  if(L!=)

    {

      for(i=,j=L;j<=mid;i++,j++)a[i]=g[j]; for(;i<len;i++)a[i]=;

      for(i=,j=L;j<=R;i++,j++)b[i]=f[i+]; for(;i<len;i++)b[i]=;

      ntt(a,); ntt(b,);

      for(i=;i<len;i++)a[i]=(ll)a[i]*b[i]%mod;

      ntt(a,);

      for(i=mid+,j=i-L-;i<=R;i++,j++)f[i]=upt(f[i]+a[j]);

    }

  solve(mid+,R);

}

int main()

{

  int T=rdn(); n=rdn();

  init(); solve(,n); f[]=;

  while(T--)

    {

      int top=,ans=; bool fg=;

      for(int i=;i<=n;i++)

    {

      int tl=i-rdn()+, ct=;

      if(i==n&&tl!=)fg=; if(fg)continue;

      while(top&&sta[top].l>=tl) top--,ct++;

      if(top&&sta[top].r>=tl)fg=;

      sta[++top]=Node(tl,i);

      ans=(ll)ans*f[ct]%mod;

    }

      if(fg)puts(""); else printf("%d\n",ans);

    }

  return ;

}

巴特西

LOJ 2554 「CTSC2018」青蕈领主——结论（思路）+分治FFT

最新文章

热门文章