题解 P5825 【排列计数】

Karry5307 · 2019-12-17 20:13:22 · 题解

题意

我的题面写的挺直白的，不再多过解释。

\texttt{Data Range:}n\leq 2\times 10^5

题解

对于长度为 n 且有 k 个上升的排列定义为欧拉数 \left\langle\begin{matrix}n\\k\end{matrix}\right\rangle。

其实这个东西的英文名叫 \texttt{Eulerian Number}，所以说别把它和另一个欧拉数搞混淆了。

首先我们有一个非常 \texttt{naive} 的想法是 \texttt{dp}。

考虑从长度为 n-1 的排列中插入一个 n 来构造长度为 n 的排列。

然后有四种情况。

在排列的左端插入一个 n，这样不产生任何升高，所以这种情况从 \left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle 转移来。
在排列的右端插入一个 n，这样会产生一个升高，所以这种情况由 \left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle 转移来。
在某一个位置 i 和 i+1 中间插入 n，其中 P_i<P_{i+1}，那么这里会产生一个升高，同时会破坏原来的一个升高，所以总的升高是不变的。所以之前的排列要有 k 个升高，所以，这种情况由 k\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle转移来。
在某一个位置 i 和 i+1 中间插入 n，其中 P_i>P_{i+1}，那么这里会产生一个升高，但是不会破坏任何原有的升高，所以总而言之产生了一个升高。所以之前的排列要有 k-1 个升高，所以，这种情况由 (n-k-1)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle转移来。

所以，我们有一个简单的递推式：

\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle

然后，我们来证明一个非常重要的恒等式叫做 \texttt{Worpitzky} 恒等式，为

x^n=\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n}

在证明这个之前，我们先来证明一个小小的东西做热身：

x\binom{x+k}{n}=(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}

两边强行展开一下就好了，然后我们用数学归纳法证。

首先，要证明的柿子在 n=0 时成立。

然后，若 x^n=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n} 成立，则只需证 x^{n+1}=\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1} 也成立。

于是，我们来推推柿子，首先从一个很弱智的东西开始：

x^{n+1}=x\cdot x^n=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle x\binom{x+k}{n}

然后我们热身的东西就派上用场啦：

x^{n+1}=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\left ((k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}\right )

一步拆括号，有

x^{n+1}=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle (k+1)\binom{x+k}{n+1}+\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle(n-k)\binom{x+k+1}{n+1}

然后，康康右边，我们用之前的递推式，有

\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n+1}\left ((k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle+(n+1-k)\left\langle\begin{matrix}n\\k-1\end{matrix}\right\rangle\right )\binom{x+k}{n+1}

意识到在 k=n+1 处被求和式值为 0，所以适当调整一下上界，并一步拆括号

\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n}(k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n+1}+\sum\limits_{k=0}^{n}(n+1-k)\left\langle\begin{matrix}n\\k-1\end{matrix}\right\rangle\binom{x+k}{n+1}

右边的和式用 k-1 代替 k，得到

\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n}(k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n+1}+\sum\limits_{k=-1}^{n-1}(n-k)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k+1}{n+1}

然后发现这个 k=-1 和 k=n 时右边和式中被求和式值为 0，调整一下上下界即可证明该恒等式。

然后就是有限微积分啊哈哈哈。首先我们注意到

\Delta\left (\binom{x+k}{n}\right)=\binom{x+k}{n-1}

然后做多次差分即可得到这样一个东西：

\Delta^m\left (\binom{x+k}{n}\right)=\binom{x+k}{n-m}

很好，于是我们可以前进一步了

\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n-m}=\Delta^m(x^n)=\sum\limits_{j}\binom{m}{j}(-1)^{m-j}(x+j)^n

我们将 x=0 代入，并使用一个非常常见的公式

m!\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum\limits_{k}\binom{m}{k}k^n(-1)^{m-k}

于是，有

\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{k}{n-m}=m!\left\{\begin{matrix}n\\m\end{matrix}\right\}

很好，我们又迈出了一步。接下来是关键的一步。

我们两边对 m 求和，有

\sum\limits_{m}\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{k}{n-m}=\sum\limits_{m}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}

乘上 z^{n-m}（换一个变量）

\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\sum\limits_{m}z^{n-m}\binom{k}{n-m}=\sum\limits_{m}z^{n-m}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}

然后你会发现是个二项式定理的事情，然后简单的代换一下最终我们得到

\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\sum\limits_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}\binom{n-k}{m}(-1)^{n-k-m}k!

很好。强行拆组合数

\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}\frac{(n-k)!}{m!(n-k-m)!}(-1)^{n-k-m}k!

然后，写得更加清楚一点，我们有

m!\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k}\left(\left\{\begin{matrix}n\\k\end{matrix}\right\}k!(n-k)!\right)\frac{(-1)^{n-(m+k)}}{(n-(m+k))!}

现在，我们设 f_i=i!\left\langle\begin{matrix}n\\i\end{matrix}\right\rangle， g_k=\left\{\begin{matrix}n\\k\end{matrix}\right\}k!(n-k)!， h_k=\frac{(-1)^{n-k}}{(n-k)!}，然后有

f_i=\sum\limits_{k}g_{k}h_{i+k}

把 h 翻转一下做个卷积再把 f 翻转回来即可。时间复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=524351,MOD=998244353,G=3,INVG=332748118;
ll fd,cnt,limit;
ll f[MAXN],g[MAXN],rev[MAXN],fact[MAXN],finv[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
    li res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=1ll*res*base%MOD;
        }
        base=1ll*base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
    ll cur=0,res=0,omg=0;
    for(register int i=0;i<cnt;i++)
    {
        if(i<rev[i])
        {
            swap(cp[i],cp[rev[i]]);
        }
    }
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1,res=qpow(inv==1?G:INVG,(MOD-1)/i);
        for(register ll *p=cp;p!=cp+cnt;p+=i)
        {
            omg=1;
            for(register int j=0;j<cur;j++)
            {
                ll t=1ll*omg*p[j+cur]%MOD,t2=p[j];
                p[j+cur]=(t2-t+MOD)%MOD,p[j]=(t2+t)%MOD;
                omg=1ll*omg*res%MOD;
            }
        }
    }
    if(inv==-1)
    {
        ll invl=qpow(cnt,MOD-2);
        for(register int i=0;i<=cnt;i++)
        {
            cp[i]=1ll*cp[i]*invl%MOD;
        }
    }
}
inline void setup(ll cnt)
{
    fact[0]=finv[0]=1;
    for(register int i=1;i<cnt;i++)
    {
        fact[i]=(li)fact[i-1]*i%MOD;
    }
    finv[cnt-1]=qpow(fact[cnt-1],MOD-2);
    for(register int i=cnt-2;i;i--)
    {
        finv[i]=(li)finv[i+1]*(i+1)%MOD;
    }
}
int main()
{
    setup((fd=read()+1)+10);
    for(register int i=0;i<fd;i++)
    {
        f[i]=(li)(i&1?MOD-1:1)*finv[i]%MOD;
        g[i]=(li)qpow(i,fd-1)*finv[i]%MOD;
    }
    cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
        cnt<<=1,limit++;
    }
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(f,cnt,1),NTT(g,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        f[i]=(li)f[i]*g[i]%MOD,g[i]=0;
    }
    NTT(f,cnt,-1);
    for(register int i=0;i<fd;i++)
    {
        f[i]=(li)f[i]*fact[i]%MOD*fact[fd-1-i]%MOD;
        g[i]=(fd-1-i)&1?MOD-finv[fd-1-i]:finv[fd-1-i];
    }
    for(register int i=fd;i<cnt;i++)
    {
        f[i]=g[i]=0;
    }
    reverse(g,g+fd),NTT(f,cnt,1),NTT(g,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        f[i]=(li)f[i]*g[i]%MOD;
    }
    NTT(f,cnt,-1),reverse(f,f+fd);
    for(register int i=0;i<fd;i++)
    {
        printf("%d ",(li)f[i]*finv[i]%MOD); 
    }
}