首先，连续段要知道结论：

连续段要么不交，要么包含

所以是一棵树！每个位置的father是后面第一个包含它的

树形DP！

设dp[x]，x为根的子树，（设管辖的区间长度为len，也即L[x]），用1~len的数填充，满足L的方案数

也就是，每个son内部合法，

给每个son分配标号区间，使得相邻儿子不会再接在一起

不会再接在一起？

 所以可以把每个儿子看成单独一个点，就划归成了：1,1,1,1,...len的方案数！

 

设f[i]表示，长度为i+1的1,1,1,1....i+1的序列的合法方案数。

$dp[x]=(\Pi dp[son])\times f[L[x]]$

归纳一下，可得$ans=\Pi f[|son(x)|]$,$|son(x)|$表示x的儿子个数

 

求f[n]？

考虑变成排列的逆！

（也就是把映射矩阵的横纵坐标意义交换）

这样，n+1成为了天然的分割点。

 

f[n-1]中，填入1，

要么之前合法。

要么1分开了一些东西

|son(x)|可以直接单调栈

 

注意，Poly每次clear需要重新resize

 

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int sub(int x,int y){ return ad(x,mod-y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}template
           
            il int ad(const int a,const int b,const Args &...args) { return ad(ad(a,b),args...);}template
            
             il int mul(const int a,const int b,const Args &...args) { return mul(mul(a,b),args...);}} using namespace Modulo;namespace Miracle{const int N=50000+5;const int G=3;const int GI=332748118;int n,T;int L[N];struct Poly{ vector
             
              f; Poly(){f.clear();} il int &operator[](const int &x){assert(x
              
               >1]>>1)|((i&1)?m>>1:0); } return m;}void NTT(Poly &f,int c){ int n=f.size(); for(reg i=0;i
               
                >1; divi(l,mid); // cout<<" divi ---------------------------"<
                
                 <<" "<
                 
                  <
                  
                   =i-L[i]+1) ++son,--top; // cout<<" ii "<
                   <<" son "<
                    
                     <
                     
                      =i-L[i]+1) fl=false; } sta[++top]=i; ans=mul(ans,f[son]); } if(!fl) ans=0; printf("%d\n",ans); } return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/
                     
                    
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

树形结构！

然后递归为子问题。

递归为子问题，把。。。看成。。。。

本质就是“缩点”找相似结构。或者归纳