オイラー多項式

1 参考文献
2 オイラー多項式
3 $\sum_{m=1}^n m^d r^m, \sum_{m=1}^\infty m^dr^m$ の計算

参考文献

Enumerative Combinatorics (Stanley)
無限和を計算するyosupo judgeの問題（kyopro friendsさん）
[多項式・形式的べき級数] 高速に計算できるものたち（maspyさん）

$f \in [m]^{[d]}$ に対して、

$f(w_1) \geq f(w_2) \geq \cdots \geq f(w_m)$
$w_i > w_{i+1}$ ならば $f(w_i) > f(w_{i+1})$

を満たす唯一の置換 $w \in \mathfrak{S}_d$ が存在します。$f$ を $w$ compatible と呼びます。$w$ を固定したときの $w$ compatible な $f$ の個数を数えましょう。例えば、$$m \geq f(w_1) \geq f(w_2) > f(w_3) \geq f(w_4) > f(w_5) \geq 1$$を満たす $f$ の個数と、$$m-3 \geq g(w_1) \geq g(w_2) \geq g(w_3) \geq g(w_4) > g(w_5) \geq 0$$を満たす $g \in \{0, \ldots, m-3\}^{[5]}$ の個数は同じで、
\begin{align}
&f(w_1)=g(w_1)+3 \\
&f(w_2)=g(w_2)+3 \\
&f(w_3)=g(w_3)+2 \\
&f(w_4)=g(w_4)+2 \\
&f(w_5)=g(w_5)+1
\end{align}が全単射です。$w_i > w_{i+1}$ を満たす $i$ の個数を $\mathrm{des}(w)$ と置くと、このような $g$ は
$(-1)^{m-\mathrm{des}(w)-1}{-d-1 \choose m-\mathrm{des}(w)-1}$ 通りあります。従って、$A_d(x) := \sum_{w \in \mathfrak{S}_d} x^{\mathrm{des}(w)+1}$ と置くと、$$\sum_{m \geq 1} m^dx^m = \frac{A_d(x)}{(1-x)^{d+1}}$$が成り立ちます。一般論として、$a_n$ が $n$ の $d$ 次式のとき、$f(x) = \sum a_n x^n$ の $d+1$ 回差分 $f(x)(1-x)^{d+1}$ は $d$ 次以下になりますが、その特殊系です。$A_d(x)$ をオイラー多項式と呼びます。$\sum_{m \geq 1} m^dx^d$ と $(1-x)^{d+1}$ の畳み込みにより、$O(d \log(d))$ で $A_d(x)$ が求まります（JOI出題例）。$w$-compatible の半順序集合に対する一般化は $(P, \omega)$ parition として知られています。

$\sum_{m=1}^n m^d r^m, \sum_{m=1}^\infty m^dr^m$ の計算

形式的べき級数 $f, g$ の積 $h = fg$ が $d$ 次多項式のとき、$\bmod x^{d+1}$ で畳み込みを計算しても結果は変わりません。従って、有理数 $x=r$ $(0 < r < 1)$ を $\mathbb{F}_p$ 係数で代入した値は、累積和を用いて $O(d\log(p))$ で求められます。$f = \sum_{i=1}^\infty m^dx^m, g=(1-x)^{1+d}$ とすると、$f(r)$ は $O(d\log(p))$ で求められます。$f(x) = \sum_{m=1}^n m^d x^m, g(x) = (1-x)^{d+1}$ の場合、$h = fg$ は、$d+1$ 次多項式 $h_1, h_2$ を用いて、$$h = h_1+x^{n+1}h_2$$ と表せます。従って、同様に累積和で $O(d\log(p))$ で $f(r)$ が求まります。$f$ は多項式なので、$0 < r < 1$ に限らず代入できます。ただし、$r = 1$ の場合は $(1-r)^{d+1} = 0$ なので、逆元が取れず、場合分けが必要です（$r \to 1$ を取ったりして同じ議論でできないのかなぁ）。$Q(n)=\sum_{m=1}^{n} m^d r^m$ は $n$ の高々 $d+1$ 次式なので、$Q(0),Q(1),\ldots,Q(d)$ から $Q(n)$ をラグランジュ補間すればよいです。$\sum_{i=0}^\infty r^i i^d = \left[\frac{x^d}{d!}\right] 1 / (1 – r \exp(rx))$ でも O(n log n) にはなります。