Integration

解説

$I_n$ の値を直接求めることは難しいです。そのため、次の漸化式を考えます。

$$= [x^{n+1}(-e^{-x})]^{1}_{0}+(n+1)\int_{0}^{1}{x^ne^{-x}dx}$$ $$\displaystyle =-e^{-1}+(n+1)I_n$$

この漸化式を利用して答えの値を求めても良いですが、ここでは数式変形による工夫を考えていきます。

$$\displaystyle I_{n+1} =-e^{-1}+(n+1)I_n$$ $$\displaystyle \frac{I_{n+1}}{(n+1)!} =\frac{-e^{-1}}{(n+1)!}+\frac{I_n}{n!}$$

ここで、$\displaystyle x_n = \frac{I_{n}}{n!},c =\frac{-e^{-1}}{(n+1)!}$ とおくと、$\displaystyle x_{n+1} = c + x_n$　より、

$$\begin{aligned} x_n = \begin{cases} x_0+\displaystyle\sum_{k=0}^{n-1}\frac{-e^{-1}}{(k+1)!} & (n \ge 1) \\ x_0 & (n = 0) \end{cases} \end{aligned}$$

$x_n=\displaystyle x_0-e^{-1}\sum^{n}_{k=1}{\frac{1}{k!}}$

ここで、 $\displaystyle x_0 = \frac{I_0}{0!} = -e^{-1}+1$ であるから、

$$\displaystyle \frac{I_n}{n!}= (-e^{-1}+1)-e^{-1}\sum^{n}_{k=1}{\frac{1}{k!}} = 1-e^{-1}\sum^{n}_{k=0}{\frac{1}{k!}}$$ $$\displaystyle I_n= n!({1-e^{-1}\sum^{n}_{k=0}{\frac{1}{k!}}}) = n! - e^{-1}\sum^{n}_{k=0}{\frac{n!}{k!}}$$

よって、$\displaystyle a=-\sum^{n}_{k=0}{\frac{n!}{k!}},b=n!$ です。

ここで、$\displaystyle\sum^{n}_{k=0}{\frac{n!}{k!}}$ の値を高速に求めることを考えます。この値を $S_n$ とします。ここで、 $\displaystyle S_{n+1} = \sum^{n+1}_{k=0}{\frac{(n+1)!}{k!}} = (n+1)\sum^{n}_{k=0}{\frac{n!}{k!}}+\frac{(n+1)!}{(n+1)!} = (n+1)S_n+1$ であり、この漸化式から $S_0$ から $S_n$ までの値は$O(N)$ で前計算できます。$0!$ から $n!$ の値も$O(N)$ で前計算できるので、全体として計算量は $O(N+Q)$ となり、実行時間制限に間に合います。

追記

$a,b$ の値を

$$\displaystyle I_{n+1}=-e^{-1}+(n+1)I_n$$

を用いて計算してみます。ここで、$I_n$ の $a,b$ の値を

$$\left( \begin{array}{c} a_n \\ b_n \\ \end{array} \right)$$

という風にベクトルと行列で表現すると、

$$\left( \begin{array}{c} a_{n+1} \\ b_{n+1} \\ \end{array} \right) = \begin{pmatrix} n+1 & 0 \\ 0 & n+1 \end{pmatrix} \left( \begin{array}{c} a_{n} \\ b_{n} \\ \end{array} \right)+ \left( \begin{array}{c} -1 \\ 0 \\ \end{array} \right)$$

となります。これをそのまま前計算に利用することでも計算量 $O(N+Q)$ を達成できます。(なんなら $a_n,b_n$ に分解できるので、こっちのほうがかなり楽です。)