51nod 1514 美妙的序列

Description

长度为n的排列，且满足从中间任意位置划分为两个非空数列后，左边的最大值>右边的最小值。问这样的排列有多少个%998244353

题面

Solution

正难则反

\(f[n]=n!-\)不满足条件的排列

不满足条件的排列一定是这样的:

存在一个断点 \(L\),使得 \([1,L]\) 中的数的值域也为 \([1,L]\),\([L+1,n]\) 的值域为 \([L+1,n]\)

但是一个不合法的排列,可能存在很多个断点 \(L\) 满足上述条件,会算重很多次,所以我们要强制前半部分是合法的,方案数为 \(f[i]\)

\(f[n]=\sum_{i=1}^{n-1}f[i]*(n-i)!\)

这个式子用分治 \(*NTT\) 求解就好了

#include<bits/stdc++.h>

using namespace std;

const int N=400005,mod=998244353;

int T,q[N],Fac[N],f[N],n,m,L,R[N],inv;

inline int qm(int x,int k){

	int sum=1;

	while(k){

		if(k&1)sum=1ll*sum*x%mod;

		x=1ll*x*x%mod;k>>=1;

	}return sum;

}

inline void NTT(int *A,int o){

	for(int i=0;i<n;i++)if(i<R[i])swap(A[i],A[R[i]]);

	for(int i=1;i<n;i<<=1){

		int t0=qm(3,(mod-1)/(i<<1)),x,y;

		for(int j=0;j<n;j+=i<<1){

			int t=1;

			for(int k=0;k<i;k++,t=1ll*t*t0%mod){

				x=A[j+k];y=1ll*t*A[j+k+i]%mod;

				A[j+k]=(x+y)%mod;A[j+k+i]=(x-y+mod)%mod;

			}

		}

	}

	if(o==-1)reverse(A+1,A+n);

}

inline void mul(int *A,int *B){

	NTT(A,1);NTT(B,1);

	for(int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mod;

	NTT(A,-1);

}

int A[N],B[N];

inline void solve(int l,int r){

	if(l==r){f[l]=(Fac[l]-f[l]+mod)%mod;return ;}

	int mid=(l+r)>>1;

	solve(l,mid);

	n=1;m=(r-l+1);

	for(n=1,L=0;n<=m;n<<=1)L++;inv=qm(n,mod-2);

	for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)),A[i]=B[i]=0;

	for(int i=l;i<=mid;i++)A[i-l]=f[i];

	for(int i=1;i<m;i++)B[i]=Fac[i];

	mul(A,B);

	for(int i=mid+1;i<=r;i++)f[i]=(f[i]+1ll*A[i-l]*inv)%mod;

	solve(mid+1,r);

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  scanf("%d",&T);

  int n=0;

  for(int i=1;i<=T;i++)scanf("%d",&q[i]),n=max(n,q[i]);

  Fac[0]=1;for(int i=1;i<=n;i++)Fac[i]=1ll*Fac[i-1]*i%mod;

  solve(1,n);

  for(int i=1;i<=T;i++)printf("%d\n",f[q[i]]);

  return 0;

}