题目大意

　　对于一个长度为 \(n\) 的排列 \(p\)，我们称一个区间 \([l,r]\) 是连续的当且仅当 \((\max_{l\leq i\leq r}a_i)-(\min_{l\leq i\leq r}a_i)=r-l\)。

　　对于两个排列 \(p_1,p_2\)，我们称这两个排列是等价的，当且仅当他们的长度相同且连续区间的集合相同。

　　给你 \(n\)，对于 \(1\leq i\leq n\)，所有求 \(i\) 阶排列形成的等价类个数对 \(p\) 取模的值。

　　\(n\leq 100000,p=k\times2^{18}+1,k\in \mathbb {N},p\) 是质数。

题解

　　对于一个区间 \([l,r]\)，如果这个区间的所有子区间都是连续的，就称这个区间为强连续区间。

　　每次我们找一个最大的强连续区间，把这个区间内所有点缩到一起。

　　如果找不到，就找一个最小的连续区间，把这个区间内所有点缩到一起。

　　这个过程就形成了一个树结构。

• 总共有 \(n\) 个叶子。
• 对于一个代表强连续区间的点，这个点的儿子个数 \(\geq 2\)。
• 对于一个代表连续区间的点，这个点的儿子个数 \(\geq 4\)。（可以发现，长度为 \(\leq 3\) 的序列是一定有强连续区间的。）

　　每一个排列 \(p\) 对应了一棵树。

　　对于一棵树，可以构造出一个排列 \(p\)。

　　那么就只用对这棵树计数了。

　　显然可以 \(O(n^2)\) DP。

　　记 \(f_i\) 为长度为 \(i\) 的排列的方案数，\(F(x)=\sum_{i\geq 0}f_ix^i\)，那么就有：

\[ F(x)=\frac{(F(x)^2+F(x)^4)}{1-F(x)}+x \]

　　用牛顿迭代法解这个方程即可。

\[ (F(x)^2+F(x)^4)\frac{1}{1-F(x)}-F(x)+x=0\\ G(y)=(y^2+y^4)\frac{1}{1-y}-y+x\\ G'(y)=(2y+4y^3)\frac{1}{1-y}+(y^2+y^4)(-\frac{1}{(1-y)^2})(-1)-1\\ G(F(x))\equiv 0\pmod {x^n}\\ G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x)) \pmod {x^n}\\ F(x)\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod {x^n}\\ \]

　　时间复杂度：\(O(n\log n)\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             //using namespace std;using std::min;using std::max;using std::swap;using std::sort;using std::reverse;using std::random_shuffle;using std::lower_bound;using std::upper_bound;using std::unique;using std::vector;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef std::pair
             
               pii;typedef std::pair
              
                pll;void open(const char *s){#ifndef ONLINE_JUDGE char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}void open2(const char *s){#ifdef DEBUG char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}int upmin(int &a,int b){if(b
               
                a){a=b;return 1;}return 0;}const int N=270000;ll p,g;ll fp(ll a,ll b){ ll s=1; for(;b;b>>=1,a=a*a%p) if(b&1) s=s*a%p; return s;}namespace ntt{ const int W=262144; int rev[N]; int *w[20]; void init() { ll s=fp(g,(p-1)/W); w[18]=new int[1<<17]; w[18][0]=1; for(int i=1;i
                
                 =1;i--) { w[i]=new int[1<<(i-1)]; for(int j=0;j<1<<(i-1);j++) w[i][j]=w[i+1][j<<1]; } } void ntt(ll *a,int n,int t) { for(int i=1;i
                 
                  >1]>>1)|(i&1?n>>1:0); if(rev[i]>i) swap(a[i],a[rev[i]]); } for(int i=2,l=1;i<=n;i<<=1,l++) for(int j=0;j
                  
                   >1); static ll a1[N],a2[N]; for(int i=0;i
                   
                    <<1;i++) a1[i]=a2[i]=0; for(int i=0;i
                    
                     >1;i++) a2[i]=b[i]; ntt(a1,n<<1,1); ntt(a2,n<<1,1); for(int i=0;i
                     
                      <<1;i++) a1[i]=a2[i]*(2-a1[i]*a2[i]%p)%p; ntt(a1,n<<1,-1); for(int i=0;i
                      
                       >1); static ll f1[N],f2[N],f3[N],f4[N],f5[N],a1[N],a2[N],a3[N],a4[N]; for(int i=0;i