uyhip2016 June

r_64 posted @ 2016年6月30日 13:37 in 未分类 with tags uyhip , 810 阅读

好不容易在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 xy MS / 2 rnd

就可以7次之内出解辣


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter