首页 > 代码库 > NTT【51nod】1514 美妙的序列

NTT【51nod】1514 美妙的序列

2024-08-15 16:29:16   219人阅读

题意：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)

多项式求逆即可

 

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 typedef long long ll; 4 using namespace std; 5 const int N = 262144, K = 17; 6 int n, m, i, k; 7 int a[N+10], b[N+10], tmp[N+10], tmp2[N+10]; 8 int P = 998244353, G = 3, g[K+1], ng[K+10], inv[N+10], inv2; 9 int pow(int a,int b){int t=1;for(;b;b>>=1,a=(ll)a*a%P)if(b&1)t=(ll)t*a%P;return t;}10 void NTT(int*a,int n,int t){11     for(int i=1,j=0;i<n-1;i++){12         for(int s=n;j^=s>>=1,~j&s;);13         if(i<j)swap(a[i], a[j]);14     }15     for(int d=0;(1<<d)<n;d++){16         int m=1<<d,m2=m<<1,_w=t==1?g[d]:ng[d];17         for(int i=0;i<n;i+=m2)for(int w=1,j=0;j<m;j++){18             int&A=a[i+j+m],&B=a[i+j],t=(ll)w*A%P;19             A=B-t;if(A<0)A+=P;20             B=B+t;if(B>=P)B-=P;21             w=(ll)w*_w%P;22         }23     }24     if(t==-1)for(int i=0,j=inv[n];i<n;i++)a[i]=(ll)a[i]*j%P;25 }26 //给定a,求a的逆元b27 void getinv(int*a,int*b,int n){28     if(n==1){b[0]=pow(a[0],P-2);return;}29     getinv(a,b,n>>1);30     int k=n<<1,i;31     for(i=0;i<n;i++)tmp[i]=a[i];32     for(i=n;i<k;i++)tmp[i]=b[i]=0;33     NTT(tmp,k,1),NTT(b,k,1);34     for(i=0;i<k;i++){35     b[i]=(ll)b[i]*(2-(ll)tmp[i]*b[i]%P)%P;36     if(b[i]<0)b[i]+=P;37     }38     NTT(b,k,-1);39     for(i=n;i<k;i++)b[i]=0;40 }41 int main(){42     for(g[K]=pow(G,(P-1)/N),ng[K]=pow(g[K],P-2),i=K-1;~i;i--)43         g[i]=(ll)g[i+1]*g[i+1]%P,ng[i]=(ll)ng[i+1]*ng[i+1]%P;44     for(inv[1]=1,i=2;i<=N;i++)inv[i]=(ll)(P-inv[P%i])*(P/i)%P;inv2=inv[2];45     int len = 1;46     while(len <= 100000) len <<= 1;47     a[0] = 1;48     for(int i = 1; i < len; i++)49         a[i] = (ll)i*a[i-1]%P;50     getinv(a, b, len);51     for(int i = 0; i < len; i++)52         b[i] = (-b[i]+P)%P;53     b[0]++;54     int t, n; scanf("%d", &t);55     while(t--){56         scanf("%d", &n);57         printf("%d\n", b[n]);58     }59     return 0;60 }
View Code

 

NTT【51nod】1514 美妙的序列


联系
我们