[数学记录]51nod1514 美妙的序列
command_block
2020-11-21 23:38:12
**题意** : 对于一个长度为 $n$ 的排列 $P$ ，若满足对于所有 $k=1...(n-1)$ ，后 $n-k$ 个数中，存在一个数小于前 $k$ 个数，则称排列是美妙的。
给出 $n$ ，求长度为 $1...n$ 的“美妙的排列”的数量。
$n\leq 10^5$，时限$\texttt{2s}$。
------------
考虑一个排列是“美妙的”的充要条件。
若对于某个 $k$ ，后 $n-k$ 个数全部大于前面的 $k$ 个，这等价于前 $k$ 个数组成排列。
设 $t(P)$ 为排列 $P$ 的最长排列前缀 (不包括本身)。
不难发现，美妙的充要条件是 $t(P)=0$。
设 $f[n]$ 为长度为 $n$ 的“美妙的排列”的数量。
考虑枚举 $i=t(P)\geq 1$ 减去不美妙的排列。
可以先安排一个长度为 $i$ 的排列，这部分方案数为 $i!$。
然后接上一个 $t(P)=0$ 的长度为 $n-i$ 的(美妙)排列，就能保证 $i$ 是最长排列前缀。
有递推式 $f[n]=n!-\sum\limits_{i=1}^{n-1}i!f[n-i]$
移项可得 $\sum\limits_{i=1}^{n}i!f[n-i]=n!$
当 $n=0$ 时有 $0!=1$。
设 $G(x)=\sum\limits_{i=1}x^ii!,\ F(x)=\sum\limits_{i=1}f[i]x^i$
则有 $G(x)=1+F(x)G(x)$ ,即 $F(x)=1-\dfrac{1}{G(x)}$。
多项式求逆即可。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define ull unsigned long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int _G=3,mod=998244353,Maxn=135000;
ll powM(ll a,int t=mod-2){
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;t>>=1;
}return ans;
}
const int invG=powM(_G);
int tr[Maxn<<1],tf;
void tpre(int n){
if (tf==n)return ;tf=n;
for(int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *g,bool op,int n)
{
tpre(n);
static ull f[Maxn<<1],w[Maxn<<1]={1};
for (int i=0;i<n;i++)f[i]=(((ll)mod<<5)+g[tr[i]])%mod;
for(int l=1;l<n;l<<=1){
ull tG=powM(op?_G:invG,(mod-1)/(l+l));
for (int i=1;i<l;i++)w[i]=w[i-1]*tG%mod;
for(int k=0;k<n;k+=l+l)
for(int p=0;p<l;p++){
int tt=w[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
if (l==(1<<10))
for (int i=0;i<n;i++)f[i]%=mod;
}if (!op){
ull invn=powM(n);
for(int i=0;i<n;++i)
g[i]=f[i]%mod*invn%mod;
}else for(int i=0;i<n;++i)g[i]=f[i]%mod;
}
void px(int *f,int *g,int n)
{for(int i=0;i<n;++i)f[i]=1ll*f[i]*g[i]%mod;}
int _g1[Maxn<<1];
#define sav _g1
void times(int *f,int *g,int len,int lim)
{
int n=1;for(n;n<len+len;n<<=1);
cpy(sav,g,n);
for(int i=len;i<n;i++)sav[i]=0;
NTT(f,1,n);NTT(sav,1,n);
px(f,sav,n);NTT(f,0,n);
for(int i=lim;i<n;++i)f[i]=0;
clr(sav,n);
}
void invp(int *f,int m)
{
static int w[Maxn<<1],r[Maxn<<1];
int n;for (n=1;n<m;n<<=1);
w[0]=powM(f[0]);
for (int len=2;len<=n;len<<=1){
for (int i=0;i<(len>>1);i++)
r[i]=(w[i]<<1)%mod;
cpy(sav,f,len);
NTT(w,1,len<<1);px(w,w,len<<1);
NTT(sav,1,len<<1);px(w,sav,len<<1);
NTT(w,0,len<<1);clr(w+len,len);
for (int i=0;i<len;i++)
w[i]=(r[i]-w[i]+mod)%mod;
}cpy(f,w,m);clr(sav,n+n);clr(w,n+n);clr(r,n+n);
}
int T,n,m[Maxn],F[Maxn];
int main()
{
scanf("%d",&T);
for (int i=1;i<=T;i++){
scanf("%d",&m[i]);
n=max(n,m[i]);
}
n++;F[0]=1;
for (int i=1;i<=n;i++)
F[i]=1ll*F[i-1]*i%mod;
invp(F,n);
for (int i=0;i<n;i++)
F[i]=mod+(i==0)-F[i];
for (int i=1;i<=T;i++)
printf("%d\n",F[m[i]]);
return 0;
}
```