题解 P5825 【排列计数】
皎月半洒花
2019-12-17 09:06:03
### 题意
我们记一个排列$P$的升高为$k$当且仅当存在$k$个位置$i$使得$P_i<P_{i+1}$
现在给定排列长度$n$，对于所有整数$k\in [0,n]$求有多少个排列的升高为$k$。
$n\leq 200,000$
### $\rm Sol$
首先写一个递推式，令$f(n,k)$表示答案，则有
$$
f(n,k)=(n-k) \cdot f(n-1,k-1) + (k + 1) \cdot f(n-1,k)
$$
其意义是，考虑将这个序列的升高与圆排列的升高之间建立映射。定义顺时针为正方向（其实顺时针逆时针是对称的）。
* 一个长为$n$、升高为$k$的**圆排列**，有$n-k$种断开的方式，使之变成一个长为$n$，升高为$k$的**序列**；
* 一个长为$n$，升高为$k+1$的**圆排列**，有$k+1$种断开方式，使之变成一个长为$n$，升高为$k$的**序列**。
* 一个长为$n$，升高为$k$的**圆排列**，删除掉值为$n$的那一项，则一定会删除掉恰好$1$个升高，所以对应一个长为$n-1$，升高为$k-1$的**序列**。
* 一个长为$n$，升高为$k+1$的**圆排列**，删除掉值为$n$的那一项，则一定会删除掉恰好$1$个升高，所以对应一个长为$n-1$，升高为$k$的**序列**。
显然后面两条的逆操作同样成立，所以是双射。
然而其实后面两条是等价的，只是平移了一下$k$…233
~~然后就可以获得一个$n^2$算法，得到$0pts$的好成绩了~~
_____
之后就需要用到黑宝书—— ~~《混凝土数学》~~ 《具体数学》了。
具体数学的$6.2$提到了这个数列（表），有一个公式是长这样的：
$$
f(n,m)=\sum _{k=0}^{m}\binom{n+1}{k}(m+1-k)^n(-1)^k
$$
然而~~混凝土~~编者当时都没有给出这东西是怎么来的，~~并且咱也不怎么会推~~ ，于是或许就可以当个结论记住？
不过如果要是证明它是对的倒挺简单……即考虑把上式记作这个数列**关于$\bold n$的$\bold m$展开**，那么大家手算一下发现这东西跟关于$n-1$的$m-1$展开和关于$n-1$的$m$展开，存在递推形式，且递推形式和一开始给出的递推式相同；加之初值一样，所以成立。
……然后就是计算生成函数，考虑如何计算第$n$行的$\bold {OGF}$
通过观察法，可以发现作为第$m$项系数的这个和式，其中$\sum _{k=0}^{m}\binom{n+1}{k}(-1)^k$是一个二项式的展开，再将$(m+1-k)^n$这东西对称处理一下，~~通过简单的结合律~~ 就可以得到它的$\bold{OGF}$:
$$
(1-x)^{n+1}\sum_{k=0}^{n} (k+1)^nx^{k}
$$
~~上述过程完全可以去OEIS上找，可以简化一系列猜结论+验证结论的过程~~
然后就是一个多项式快速幂了……
然而朴素的多项式快速幂是$\log^2$，~~再加上NTT本身>O(log n)的常数~~发现并不可以过……但实际上$(1-x)^n$状物就是个杨辉三角，于是组合数算一下就完了.jpg
（截止到我写下这一行字为止，我的code还是最快的）
```cpp
int main(){
cin >> PL ;
K = PL += 1 ; int i, j ;
for (i = 0 ; i < 19 ;++ i){
rr int *rua = gg[i] ; rua[0] = 1 ;
rr int gi = rua[1] = expow(3, 998244352/(1 << (i + 1))) ;
for (j = 2 ; j < (1 << i) ; ++ j)
rua[j] = 1ll * rua[j - 1] * gi % P ;
}
M = 1 ;
while (M <= (PL << 1)) M <<= 1, ++ l ;
for (i = 0 ; i < M ; ++ i)
R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
F[0] = 1, F[1] = -1,
A[0] = 1, Fac[0] = Inv[0] = 1 ;
for (i = 1 ; i <= PL ; ++ i)
Fac[i] = 1ll * Fac[i - 1] * i % P ;
Inv[PL] = expow(qwq = Fac[PL], P - 2) ;
for (i = PL - 1 ; i ; -- i)
Inv[i] = 1ll * Inv[i + 1] * (i + 1) % P ;
for (i = 0 ; i <= PL ; ++ i)
A[i] = (i & 1) ? P - Comb(i) : Comb(i) ;
for (i = 0 ; i <= PL ; ++ i)
S[i] = expow(i + 1, PL - 1) ;
NTT(A, M, 1), NTT(S, M, 1) ;
for (i = 0 ; i <= M ; ++ i)
S[i] = 1ll * S[i] * A[i] % P ;
NTT(S, M, -1) ;
for (i = 0 ; i < PL ; ++ i) printf("%d ", S[i]) ;
return 0 ;
}
```
讲道理，最后是不是应该%一下出题人啊，%%%$\sf{\color{black}{K}\color{red}{arry5307}}$