NTT【51nod】1514 美妙的序列

时间：2023-03-08 20:23:31

题意：1~n 的全排列中，有多少个排列满足任意从中间切成两段后，左边段的最大值大于右边段的最小值？

例如：n为3时有3种

2 3 1

3 1 2

3 2 1

解释：比如 2 3 1

（2） （3 1） 1比2小

（2 3） （1） 1比2小

都满足上面的条件。

3 2 1

（3）（2 1） 1比3小

（32）（1）  1比3小

都满足上面的条件。

而2 1 3不满足，因为(2 1)(3)，3比左边所有的数都大。

====================================分割线====================================

首先序列为美妙的等价于不存在(1<=i<n)使得 前i个数为1~i的排列

令f[n]为长度为n的答案

则：

f[0]=0

f[i]=i!-sigma(f[j]*(i-j)!)  0<=j<i

我们将其变形

Sigma(f[j]*(i-j)!) = i!   i > 0, j=0~i

Sigma(f[j]*(i-j)!) = 0   i = 0, j=0~i

令G(x)=sigma(i!*x^i),F(x)=sigma(f[i]*x^i)

F(x)*G(x)=G(x)-1  （减一为i = 0的情况）

F(x)=(G(x)-1)/G(x)=1-1/G(x)

多项式求逆即可

 #include<cstdio>

 #include<iostream>

 typedef long long ll;

 using namespace std;

 const int N = , K = ;

 int n, m, i, k;

 int a[N+], b[N+], tmp[N+], tmp2[N+];

 int P = , G = , g[K+], ng[K+], inv[N+], inv2;

 int pow(int a,int b){int t=;for(;b;b>>=,a=(ll)a*a%P)if(b&)t=(ll)t*a%P;return t;}

 void NTT(int*a,int n,int t){

     for(int i=,j=;i<n-;i++){

         for(int s=n;j^=s>>=,~j&s;);

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

     }

     for(int d=;(<<d)<n;d++){

         int m=<<d,m2=m<<,_w=t==?g[d]:ng[d];

         for(int i=;i<n;i+=m2)for(int w=,j=;j<m;j++){

             int&A=a[i+j+m],&B=a[i+j],t=(ll)w*A%P;

             A=B-t;if(A<)A+=P;

             B=B+t;if(B>=P)B-=P;

             w=(ll)w*_w%P;

         }

     }

     if(t==-)for(int i=,j=inv[n];i<n;i++)a[i]=(ll)a[i]*j%P;

 }

 //给定a,求a的逆元b

 void getinv(int*a,int*b,int n){

     if(n==){b[]=pow(a[],P-);return;}

     getinv(a,b,n>>);

     int k=n<<,i;

     for(i=;i<n;i++)tmp[i]=a[i];

     for(i=n;i<k;i++)tmp[i]=b[i]=;

     NTT(tmp,k,),NTT(b,k,);

     for(i=;i<k;i++){

     b[i]=(ll)b[i]*(-(ll)tmp[i]*b[i]%P)%P;

     if(b[i]<)b[i]+=P;

     }

     NTT(b,k,-);

     for(i=n;i<k;i++)b[i]=;

 }

 int main(){

     for(g[K]=pow(G,(P-)/N),ng[K]=pow(g[K],P-),i=K-;~i;i--)

         g[i]=(ll)g[i+]*g[i+]%P,ng[i]=(ll)ng[i+]*ng[i+]%P;

     for(inv[]=,i=;i<=N;i++)inv[i]=(ll)(P-inv[P%i])*(P/i)%P;inv2=inv[];

     int len = ;

     while(len <= ) len <<= ;

     a[] = ;

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

         a[i] = (ll)i*a[i-]%P;

     getinv(a, b, len);

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

         b[i] = (-b[i]+P)%P;

     b[]++;

     int t, n; scanf("%d", &t);

     while(t--){

         scanf("%d", &n);

         printf("%d\n", b[n]);

     }

     return ;

 }

相关文章