25.9.3 闲话：欧拉数
喵仔牛奶
·
·
算法·理论
\gdef\euler#1#2{\left\langle{#1\atop #2}\right\rangle}
\gdef\Euler#1#2{\left\langle\begin{matrix}#1\\#2\end{matrix}\right\rangle}
定义 \Euler{n}{m} 为长度为 n 的 \sum_{i=2}^{n}[p_{i-1}<p_i]=m 的排列数。求 \Euler{n}{m}。
数据范围：n,m\le 10^6。
容斥，钦定 i 个位置 p_{i-1}<p_i。这些位置将序列划分为了若干连续段，设连续段长度为 l_1,l_2,\cdots,l_{n-i}，这相当于一个多重集排列，方案数为 \displaystyle\binom{n}{l_1,l_2,\cdots,l_{n-i}}。
因此所有 l 的方案数和为 [x^n](e^x-1)^{n-i}，推式子：
\begin{aligned}
\Euler{n}{m}=&\sum_{i}(-1)^{i-m}\binom{i}{m}[x^n](e^x-1)^{n-i}\\
=&\sum_{i}(-1)^{i-m}\binom{i}{m}\sum_j(-1)^{n-i-j}\binom{n-i}{j}j^n\\
=&\sum_j(-1)^{n+m+j}j^n\sum_i\binom{i}{m}\binom{n-i}{j}\\
=&\sum_j(-1)^{n+m+j}j^n\binom{n+1}{m+j+1}\\
=&\sum_{i=0}^{n-m}(-1)^i\binom{n+1}{i}(n-m-i)^n
\end{aligned}
利用 \euler{n}{m}=\euler{n}{n-m-1} 可以 \mathcal O(m) 计算。
模板题见 P2401 不等数列。可以卷积求出一行的欧拉数，见 P5825 排列计数。
那么欧拉数的 BGF 是什么呢？模仿上面的推法，令长度为 n 的排列钦定 i 个位置的系数为 x^ny^i。
一个长度为 n 的极长的钦定连续段会贡献 \frac{1}{n!}x^ny^{n-1}，不允许 n=0，因此 BGF 为：
\frac{1}{1-(e^{xy}-1)/y}=\frac{y}{1+y-e^{xy}}
设这个 BGF 为 F(x,y)，欧拉数真实的 BGF 为 G(x,y)，则 F(x,y)=G(x,y+1)，因此
G(x,y)=\frac{y-1}{y-e^{(y-1)x}}
把它展开提取出 [x^n] 也可以得到前面的通项公式。
看起来是有用的，因为有一个题 CF1687F，但是这个题也太难了。