厳密にはやってない

# 問題

https://yukicoder.me/problems/no/2391

# 解法

$X=x$ からはじめたときの期待値を $f(x)$ とおくと次をみたす．

\\[f(x)=\begin{cases}0&(x\lt 0)\\1+\int_{x-1}^{x}f(t)dt&(x\geq 0)\end{cases}\\]

$F(x):=\int_{0}^{x}f(t)dt$ とおけば次のようになる．

\\[F'(x)=\begin{cases}0&(x\lt 0)\\1+F(x)-F(x-1)&(x\geq 0)\end{cases}\\]

ここで関数列 $\{F_n\}_{n\geq 0}$ で次をみたすものを考える．

\\[\quad F_n'(x)=1+F_n(x)-F_{n-1}(x),\quad F_n(0)=F_{n-1}(1)\quad(n\geq 0)\tag{1}\\]

ただし $F_{-1}(x)\equiv 0$ とする．これらを用いると $F$ は次のように表せる．
\\[F(x)=\begin{cases}0&(x\lt 0)\\F_n(x-n)&(n\leq x\leq n+1,n\in\mathbb{Z}_{\geq 0})\end{cases}\\]

これより求める値 $f(N)$ について次が成り立つ．
\\[f(N)=F'(N)=1+F(N)-F(N-1)=1+F_N(0)-F_{N-1}(0)\tag{2}\\]

$p_n(x):=e^{-x}(F_n(x)+n+1)$ とおくと $(1)$ 式は次のようになる．

\\[\quad p_n'=-p_{n-1},\quad p_n(0)=ep_{n-1}(1)+1\quad(n\geq 0)\tag{3}\\]

これと $p_{-1}(x)\equiv 0$ より帰納的に $n\geq 0$ について $p_n$ たちは $n$ 次の多項式であることがわかる．

$p_n(x)=\sum_{k=0}^{n}a_{n,k}x^k$ とおくと $(3)$ 式は次のようになる．
\\[a_{0,0}=1,\quad a_{n,0}=1+e\sum_{i=0}^{n-1}a_{n-1,i},\quad a_{n,k}=-\frac{a_{n-1,k-1}}{k}\quad(n\geq 1,k\geq 1)\\]

$(2)$ 式より $f(N)=p_N(0)-p_{N-1}(0)=a_{N}-a_{N-1}$ なので $a_{n,0}$ が求められればよい．$a_{n,k}=\frac{(-1)^ka_{n-k,0}}{k!}$ を用い変形すると
\\[a_{0,0}=1,\quad a_{n+1,0}=1+e\sum_{k=0}^{n}\frac{(-1)^ka_{n-k,0}}{k!}\quad(n\geq 0)\\]

となる．ここで多項式列 $\{q_n(x)\}_{n\geq 0}$ を次で定める：
\\[q_0(x)=1,\quad q_{n+1}(x)=1+x\sum_{k=0}^{n}\frac{(-1)^k}{k!}q_{n-k}(x)\tag{4}\\]

このとき $q_n$ の係数は全て有理数かつ $a_{n,0}=q_n(e)$ である．解答形式を思い出せば $q_N(x)-q_{N-1}(x)$ が求められればよい．

ここで形式的冪級数として $Q(x,y):=\sum_{n\geq 0}q_n(x)y^n$ とおくと $q_N(x)-q_{N-1}(x)=[y^N](1-y)Q(x,y)$ であり， $(4)$ 式より次が成り立つ．
\\[Q(x,y)=\frac{1}{1-y}+xye^{-y}Q(x,y)\\]

整理すると
\\[Q(x,y)=\frac{1}{1-y}\cdot\frac{1}{1-xye^{-y}}\\]

なので，次のように計算できる．
\\[\begin{align*}
q_N(x)-q_{N-1}(x)
&=[y^N]\frac{1}{1-xye^{-y}}\\
&=[y^N]\sum_{n\geq 0}x^ny^ne^{-ny}\\
&=\sum_{n=0}^{N}x^n\frac{(-n)^{N-n}}{(N-n)!}
\end{align*}\\]

この係数たちは $O(N\log N)$ などで計算できる．