#P3286. Fibonacci矩阵
Fibonacci矩阵
题目描述
tangjz 喜欢 Fibonacci 数列。有一天,他想用电脑生成一个巨大的 行 列的矩阵,称之为 Fibonacci 矩阵。设 表示矩阵第 行第 列的元素,递推式如下。
$$\begin{aligned} F_{1,1}=F_{1,2}&=1,\\ F_{i,j}&=aF_{i,j-2}+bF_{i,j-1}+c && (2<j\le m),\\ F_{i,1}&=dF_{i-1,m-1}+eF_{i-1,m}+f && (i>1),\\ F_{i,2}&=dF_{i-1,m}+eF_{i,1}+f && (i>1). \end{aligned}$$其中 为给定常数。求 对 取模的结果。
输入格式
从标准输入读入数据。一行八个用空格分隔的整数 。其中 是正整数,列数满足 , 是非负整数。
输出格式
向标准输出写入结果。输出一个整数,表示 对 取模的结果。
样例 1
3 4 1 1 0 1 1 0
144
样例 2
848808952 592727016 531457588 948432766 986174065 370861260 182754678 182754678
1749721678
样例解释
第一组样例的矩阵为
$$\begin{pmatrix} 1&1&2&3\\ 5&8&13&21\\ 34&55&89&144 \end{pmatrix}.$$数据范围
| 测试点 | 数据范围 |
|---|---|
| 1 | , |
| 2 | , |
| 3 | ,, |
| 4 | , |
| 5 | ,, |
| 6 | , |
| 7 | ,,, |
| 8 | ,,, |
| 9 | ,,, |
| 10 | ,,, |
| 11 | ,, |
| 12 | ,, |
| 13 | ,,,, |
| 14 | ,,, |
| 15 | |
| 16 | |
| 17 | |
| 18 | |
| 19 | |
| 20 |