OMCE002(C) - 差分を用いる方法

$N=10000$とする．一般に多項式 $g(x)$ に対して $$g^{[0]}(x)=g(x),\quad g^{[k+1]}(x)=g^{[k]}(x+1)-g^{[k]}(x)$$ によって多項式 $g^{[0]}(x),g^{[1]}(x),g^{[2]}(x),\cdots$ を定める．$g(x)$ が $d$ 次式ならば $g^{[k]}(x)$ は $d-k$ 次式であり，特に $g^{[d+1]}(x)=0$ であることに注意する．与えられた条件から順に差分を計算すると $$f^{[k]}(n)=2^n(n+2k+1)\quad(n=0,1,\cdots,N-k)$$ となる．ここで求めるべき値は $$\begin{aligned} f(N+1)&=f(N)+f^{[1]}(N)\\ &=f(N)+f^{[1]}(N-1)+f^{[2]}(N-1)\\ &=\cdots\\ &=\sum_{k=0}^N f^{[k]}(N-k) \end{aligned}$$ と表せるので，上の式を代入して計算すると $$f(N+1)=\sum_{k=0}^N2^{N-k}(N+k+1)=2(2^N-1)(N+2)+1\equiv \mathbf{949}\pmod{N+7}$$ となる．