2583: 例1.6-1 普通递归关系
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
考虑以下定义在非负整数n上的递归关系：
$ F(n)=\begin{cases}f_0,& n=0\\f_1,&n=1\\a*F(n-1)+b*F(n-2),& otherwise\end{cases}$
其中a、b是满足以下两个条件的常数：
- $a^2+4b>0$
- $|a-\sqrt{a^2+4b}| \le 2$
给定$f_0,f_1,a，b$和$n$，请你写一个程序计算$F(n)$，可以假定$F(n)$是绝对值不超过$10^9$的整数（四舍五入）。
输入
输入文件一行依次给出5个数$f_0,f_1,a,b$和$n,f_0,f_1$是绝对值不超过$10^9$，$n$是非负整数，不超过$10^9$。另外，$a,b$是满足上述条件的实数，且$|a|,|b|≤10^6$。
输出
输出一行一个数，即$F(n)$。
样例输入 复制
0 1 1 1 20
0 1-1 0 1000000000
-1 1 4 -3 18样例输出 复制
6765
-1
387420487提示
### 提示
$F(n)=\frac{k^n(f_1-mf_0)-m^n(f_1-kf_0)}{k-m}$
其中：$m,k=\frac{a\pm \sqrt{a^2+4b}}{2}$
## 数据范围
- $0<n \le 10^9$
- $|f_0,f_1| \le 10^9$
- $a,b$为实数,且$|a,b|\le 10^6$
$F(n)=\frac{k^n(f_1-mf_0)-m^n(f_1-kf_0)}{k-m}$
其中：$m,k=\frac{a\pm \sqrt{a^2+4b}}{2}$
## 数据范围
- $0<n \le 10^9$
- $|f_0,f_1| \le 10^9$
- $a,b$为实数,且$|a,b|\le 10^6$