hdu 2065 "红色病毒"问题

考虑生成函数
 G(x) = (1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} \cdots)^2 * (1 + \frac{x^2}{2!} + \frac{x^4}{4!} \cdots)^2
考虑e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} \cdots
e^{-x} = 1 - \frac{x}{1!} + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} \cdots
G(x) = e^{2x} + (\frac{e^x-e^{-x}}{2})^2
化简可得 \begin{align*} G(x) &=e^{2x}* \frac{e^{2x} + e^{-2x}+ 2}{4} \\&= \frac{e^{4x} + 2*e^{2x}+ 1}{4}\\&= \frac{(1 + \frac{4*x}{1!} + \frac{16*x^2}{2!} + \frac{64*x^3}{3!} + \frac{256*x^4}{4!} \cdots) + 2* (1 + \frac{2*x}{1!} + \frac{4*x^2}{2!} + \frac{8*x^3}{3!} + \frac{16*x^4}{4!} \cdots) + 1}{4}\\&= (\frac{1}{4} + \frac{x}{1!} + \frac{4*x^2}{2!} + \frac{16*x^3}{3!} + \frac{64*x^4}{4!} \cdots) + (\frac{1}{2} + \frac{x}{1!} + \frac{2*x^2}{2!} + \frac{4*x^3}{3!} + \frac{8*x^4}{4!} \cdots) + \frac{1}{4} \end{align*}
所以综上第n项答案为4^{n-1}+2^{n-1} (mod\ 100)

c++代码如下:

 

1 + 3 =