[数学记录]51nod1514 美妙的序列

· · 个人记录

题意 : 对于一个长度为 n 的排列 P ，若满足对于所有 k=1...(n-1) ，后 n-k 个数中，存在一个数小于前 k 个数，则称排列是美妙的。

给出 n ，求长度为 1...n 的“美妙的排列”的数量。

------------ 考虑一个排列是“美妙的”的充要条件。 若对于某个 $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)}。

多项式求逆即可。

#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;
}