[洛谷]-5825排列计数-欧拉数、NTT-JZTXT

边界
对称性
递推形式
容斥

https://www.luogu.com.cn/problem/P5825

题意：我们记一个排列 P 的升高为 $k$ 当且仅当存在 $k$ 个位置 $i$ 使得 $P_i<P_{i+1}$。

给定排列长度 $n$，对于所有整数 $k\in [0,n]$，求有多少个排列的升高为 $k$，$1\leq n\leq 2\times 10^5$.

题解：就是要我们求欧拉数（Eulerian Number）$\left<\begin{matrix}n\\k\end{matrix}\right>$（对每个$k$），这里捋一捋欧拉数的性质。

边界

先看看边界：$\left<\begin{matrix}n\\0\end{matrix}\right>=1$，即只能从小到大排，$\left<\begin{matrix}n\\n\end{matrix}\right>=0$，这样很明显，因为$n$个数至多有$n-1$个升高。

对称性

同样不难发现类似组合数那样的对称性：$\left<\begin{matrix}n\\k\end{matrix}\right>=\left<\begin{matrix}n\\n-k-1\end{matrix}\right>$，因为假设某个排列 $P$ 有 $k$ 个升高，那么就恰有 $n-1-k$ 个下降，把排列翻转之后下降就变成了升高（升高也变成了下降）

递推形式

考虑递推形式的时候经常可以考虑增加一个元素产生的影响，假设想求$\left<\begin{matrix}n\\k\end{matrix}\right>=?$

考虑$n$移走之后是什么情况，需要说明的是增减一个元素至多改变一个“升高”，因此只要考虑 $\left<\begin{matrix}n-1\\k\end{matrix}\right>$ 和 $\left<\begin{matrix}n-1\\k-1\end{matrix}\right>$ ，如果原本有 $k$ 个上升，那么 $n$ 要么插入在上升的 $p_i<p_{i+1}$中间，要么插入在第一个位置之前，这一部分有 $k+1$ 种位置可以选择。否则如果原本有$k-1$个上升，那么就有$(n-1)-1-(k-1)=n-k-1$个下降，需要增加一个上升要么在下降的$p_i>p_{i+1}$的中间插入，要么在最后一个位置插入。综上：

\[\left<\begin{matrix}n\\k\end{matrix}\right>=(k+1)\left<\begin{matrix}n-1\\k\end{matrix}\right>+(n-k)\left<\begin{matrix}n-1\\k-1\end{matrix}\right> \]

用递推形式看起来是可以$O(nk)$地算某个位置的值了…但是如果要算一行或者一列呢？（一列似乎没什么太好的做法？——）

容斥

这一部分来自于EI的一篇博客： https://www.luogu.com.cn/blog/EntropyIncreaser/solution-p5825 ，这里大概相当于做一个更详细的注解。

欲求$\left<\begin{matrix}n\\k\end{matrix}\right>$，先考虑转化成算概率（最后按照全概率公式，乘上方案数 $n!$ 即可）进一步等价到$a_1,\dots,a_n\in (0,1)$ 恰有 $k$ 个位置$a_i<a_{i+1}$的概率，做差分$b_i=a_i-a_{i-1}(\bmod 1)$，这样一来只有在$a_i<a_{i-1}$的地方，$b_i=a_i-a_{i-1}+1$，否则$b_i=a_i-a_{i-1}$，如此 $\sum b_i=a_n+(n-1-k)$，而 $b_i$ 的这种关系也可以证明是均匀分布（没有严格证），而$a_n\in (0,1)$，所以$\sum b_i\in (n-1-k,n-k)$

问题转化成：有 $n$ 个随机变量$x_1\dots,x_n $在 $(0,1)$ 上均匀分布，$\sum x_i\in (n-1-k,n-k)$ 的概率。

更进一步只要考虑 $\sum x_i<n-k$ 的概率，所以归约成如下问题：

\[\int_0^1 d x_1\dots \int _0^1 dx_n [\sum x_i<t] \]

$[0,1]$ 的限制是很麻烦，设 $F(n,k,t)$ 表示有 $n$ 个随机变量$x_1\dots,x_n\in (0,+\infty)$，且强制$k$ 个$x_i> 1$，满足$\sum x_i<t$ 的概率，那么根据容斥原理，答案就是

\[\sum_{k=0}^n \binom{n}{k}(-1)^{k} F(n,k,t)=\sum_{k=0}^t \binom{n}{k}(-1)^{k} F(n,0,t-k)\xlongequal{\Delta}\sum_{k=0}^t \binom{n}{k}(-1)^{k} G(n,t-k) \]

因此只要考虑：

\[\begin{aligned} G(n,t)&=\int_0^{\infty}dx_1\dots \int_0^\infty dx_n [\sum_{i=1}^n x_i < t]={\color{red}\int_0^t d x_n}\int_0^{\infty }dx_1\dots \int_0^\infty dx_{n-1} [\sum_{i=1}^{n-1} x_i<t-x_n]\\ &=\int_0^t dx_n \int_0^{\infty }(\frac{t-x_n}{t})dx_1\dots \int_0^\infty (\frac{t-x_n}{t})\ dx_{n-1} [\sum_{i=1}^{n-1} x_i<t]\\ &=F(n-1,t)\int_0^t {\color{red}(\frac{t-x_n}{t})^{n-1}} dx_n =F(n-1,t) \times \frac{t}{n}=\frac{t^n}{n!} \end{aligned} \]

因此最终答案是：

\[\begin{aligned} \left<\begin{matrix}n\\k\end{matrix}\right>&= n!\times\Big( \sum_{j=0}^{n-k} \binom{n}{j}(-1)^j G(n,n-k-j)-\sum_{j=0}^{n-k-1}\binom{n}{j}(-1)^j \ G(n,n-k-1-j)\Big)\\ &=n!\times\Big( \sum_{j=0}^{n-k} \binom{n}{j}(-1)^j G(n,n-k-j){\color{red}+}\sum_{j=1}^{n-k}\binom{n}{j-1}(-1)^{\color{red}j-1} \ G(n,n-k-j)\Big)\\ &=n!\times \sum_{j=0}^{n-k}\binom{n+1}{j}(-1)^j \frac{(n-k-j)^n}{n!}= \sum_{j=0}^{n-k}\binom{n+1}{j}(-1)^j (n-k-j)^n= \end{aligned} \]

非常标准的卷积形式，一次卷积即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MOD=998244353;
const int N=1<<20;
int ksm(int a,int b){
	int ret=1;a%=MOD;
	for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;
	return ret;
}
int n,fact[N],inv_fact[N],f[N],g[N],r[N],w[N];
void ntt(int n,int *x,int op){
	rep(i,0,n-1)if(r[i]<i)swap(x[i],x[r[i]]);
	for(int i=1;i<n;i<<=1){
		int gn=ksm(op==1?3:332748118,(MOD-1)/(i<<1));
		w[0]=1;
		for(int k=1;k<i;k++)w[k]=(ll)w[k-1]*gn%MOD;
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++){
				int t1=x[j+k],t2=(ll)x[j+k+i]*w[k]%MOD;
				x[j+k]=(t1+t2)%MOD;
				x[j+k+i]=(t1-t2+MOD)%MOD;
			}
	}
	if(op==-1){
		int inv=ksm(n,MOD-2);
		rep(i,0,n-1)x[i]=(ll)x[i]*inv%MOD;
	}
}
int main(){
	fastio;
	cin>>n;
	fact[0]=1;
	rep(i,1,N-5)fact[i]=(ll)fact[i-1]*i%MOD;
	inv_fact[N-5]=ksm(fact[N-5],MOD-2);
	for(int i=N-5;i>=1;i--)inv_fact[i-1]=(ll)inv_fact[i]*i%MOD;
	rep(i,0,n){
		f[i]=(ll)fact[n+1]*inv_fact[i]%MOD*inv_fact[n+1-i]%MOD;
		if(i&1)f[i]=(MOD-f[i])%MOD;
		g[i]=ksm(i,n);
	}
	int p=1,deg=n+n;
	while(p<=deg)p<<=1;
	for(int i=0;i<p;i++)r[i]=(i&1)*(p>>1)+(r[i>>1]>>1);
	ntt(p,f,1);ntt(p,g,1);
	rep(i,0,p-1)f[i]=(ll)f[i]*g[i]%MOD;
	ntt(p,f,-1);
	rep(i,0,n)cout<<f[n-i]<<' ';
	return 0;
}