uyhip2016 June

好不容易在uyhip上看到一个拼题→_→

没有做出bonus。。日

我交过去的答案见这里。。交过去之后michael告诉我bonus做错了。

题面描述：递推式

$$f_{1,1}=f_{1,2}=f_{1,3}=1$$

$$f_{n,1}=f_{n-1,1}+f_{n-1,2},f_{n,2}=f_{n-1,1}+f_{n-1,2}+f_{n-1,3},f_{n,3}=f_{n-1,2}+f_{n-1,3}$$

给出一个计算器要求在$7$次或以内求出$f_{n,1}+f_{n,2}+f_{n,3}$的值。

拼！

首先$f_{n,1}=f_{n,3}$，然后就有$f_{n,1}=f_{n-1,1}+f_{n-1,2}$，$f_{n,2}=2f_{n-1,1}+f_{n-1,2}$。

令$F_1(x)=\sum f_{n,1}x^n$，$F_2(x)=\sum f_{n,2}x^n$。这样就有

$$F_1(x)=x(F_1(x)+F_2(x)+1)$$

$$F_2(x)=x(2F_1(x)+F_2(x)+1)$$

解得

$$F_1(x)=-\frac{x}{x^2+2x-1}$$

$$F_2(x)=-\frac{x^2+x}{x^2+2x-1}$$

令$\alpha=\sqrt{2}-1,\beta=-\sqrt{2}-1$，则$\alpha,\beta$是$x^2+2x-1$的根。

那么

$$F_1(x)=\frac{\frac{\alpha}{\beta-\alpha}}{x-\alpha}+\frac{\frac{\beta}{\alpha-\beta}}{x-\beta}$$

$$F_2(x)=x(\frac{\frac{\alpha+1}{\beta-\alpha}}{x-\alpha}+\frac{\frac{\beta+1}{\alpha-\beta}}{x-\beta})$$

然后$\frac{1}{x-\alpha}=\sum_i-\frac{x^i}{\alpha^{i+1}}$。(为什么我写这么详细。。因为自己根本不熟悉生成函数这套理论啊QAQ)

然后就可以推出

$$f_{2,n}=-\frac{\alpha+1}{\alpha^n(\beta-\alpha)}-\frac{\beta+1}{\beta^n(\alpha-\beta)}$$

然而答案是$f_{2,n+1}$(然后代入$\alpha,\beta$的值)，所以就是

$$ans_n=\frac{1}{2\alpha^{n+1}}+\frac{1}{2\beta^{n+1}}$$

接下来是喜闻乐见的7步操作。。。

首先注意这个东西就是

$$\text{rnd}(\frac{1}{2\alpha^{n+1}})=\text{rnd}(0.5\times (\frac{1}{\alpha})^{n+1})=\text{rnd}(0.5\times (\text{e}^{n+1})^{-\ln \alpha})$$

其中$\text{rnd}$表示找最近的整数。

然后预处理$x=-\ln \alpha$，执行如下操作：inc exp x^y MS / 2 rnd

就可以7次之内出解辣