#はじめに
#競プロ作問 pic.twitter.com/nf6fG2f42e
— 5％の確率で橙パフォをとるhotman (@hotmanww) September 24, 2020
これが解けるようになります。
形式的冪級数(多項式)を係数倍するテク
$\sum_{n=0}^{\infty}\frac{1}{n!}z^n=e^z$と言うのは有名な式ですよね
では$\sum_{n=0}^{\infty}\frac{n^a}{n!}z^n$は何でしょうかと言うのが今回の議題です。
これがわかれば$z$に$b$を代入することで答えを求めることが出来ます。
結論:微分してz倍する。
$\frac{dz^n}{dz}\times z=nz^n$なので、うまくいきます。
これをオイラー作用素等と呼ばれたりもするようです。
今回の場合、
$\sum_{n=0}^{\infty}\frac{n^a}{n!}z^n$は
$a=0$の時$e^z$
$a=1$の時$(e^z)'\times z$=$(z^2+z)e^z$
$a=2$の時$((z^2+z)e^z)'\times z=(z^3+3z^2+z)e^z$
と続いて行きます
この漸化式を整理すると$f_{i+1}(z)=f_i(z)+f_i'(z)$のような式になって、
$S(n+1,k)=kS(n,k)+S(n,k-1)$のような式になって、
これが第二種スターリング数だとわかります。
あとはFFT (NTT) 関連 -memo(いつもお世話になっております)
で出来ます。
おまけ
$(xd/dx)^kf(x)$はどうなるのでしょうか
$k=0$の時$f(x)$
$k=1$の時$xf'(x)$
$k=2$の時$xf'(x)+x^2f''(x)$
$k=2$の時$xf'(x)+3x^2f''(x)+x^3f'''(x)$
より第二種スターリング数を用いて
$\sum_{t=0}^kS(k,t)x^tf^{(t)}(x)$と表せます。(数学的帰納法で証明できます。)
#練習問題
sum_of_exponential_times_polynomial_limit
sum_of_exponential_times_polynomial