#P3286. Fibonacci矩阵

    ID: 2473 传统题 1000ms 512MiB 尝试: 346 已通过: 49 难度: 7 上传者: 标签>难度分类提高线性代数与代数矩阵快速幂增广状态矩阵矩阵乘法数论同余的加减乘运算CF2200tangjz原创

Fibonacci矩阵

题目描述

tangjz 喜欢 Fibonacci 数列。有一天,他想用电脑生成一个巨大的 nn 行 mm 列的矩阵,称之为 Fibonacci 矩阵。设 Fi,jF_{i,j} 表示矩阵第 ii 行第 jj 列的元素,递推式如下。

$$\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}$$

其中 a,b,c,d,e,fa,b,c,d,e,f 为给定常数。求 Fn,mF_{n,m} 对 20121820132012182013 取模的结果。

输入格式

从标准输入读入数据。一行八个用空格分隔的整数 n,m,a,b,c,d,e,fn,m,a,b,c,d,e,f。其中 n,a,b,d,en,a,b,d,e 是正整数,列数满足 m≥2m\ge2,c,fc,f 是非负整数。

输出格式

向标准输出写入结果。输出一个整数,表示 Fn,mF_{n,m} 对 20121820132012182013 取模的结果。

样例 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 n,m≤10n,m\le 10,a,b,c,d,e,f≤100a,b,c,d,e,f\le 100
2 n,m≤100n,m\le 100,a,b,c,d,e,f≤1000a,b,c,d,e,f\le 1000
3 n,m≤103n,m\le 10^3,a=b=d=e=1a=b=d=e=1,c=f=0c=f=0
4 n,m≤103n,m\le 10^3,a=b=c=d=e=f=1a=b=c=d=e=f=1
5 n,m≤109n,m\le 10^9,a=b=d=e=1a=b=d=e=1,c=f=0c=f=0
6 n,m≤109n,m\le 10^9,a=b=c=d=e=f=1a=b=c=d=e=f=1
7 n,m,a,b,d,e≤109n,m,a,b,d,e\le 10^9,a=ba=b,d=ed=e,c=f=0c=f=0
8 n,m,a,b,c,d,e,f≤109n,m,a,b,c,d,e,f\le 10^9,a=ba=b,d=ed=e,c=fc=f
9 n,m,a,b,d,e≤109n,m,a,b,d,e\le 10^9,a=da=d,b=eb=e,c=f=0c=f=0
10 n,m,a,b,c,d,e,f≤109n,m,a,b,c,d,e,f\le 10^9,a=da=d,b=eb=e,c=fc=f
11 n,m≤101000n,m\le 10^{1000},a=b=d=e=1a=b=d=e=1,c=f=0c=f=0
12 n,m≤1010000n,m\le 10^{10000},a=b=d=e=1a=b=d=e=1,c=f=0c=f=0
13 n,m≤1010000n,m\le 10^{10000},a,b,c,d,e,f≤109a,b,c,d,e,f\le 10^9,a=da=d,b=eb=e,c=fc=f
14 n,m,a,b,c,d,e,f≤1010000n,m,a,b,c,d,e,f\le 10^{10000},a=da=d,b=eb=e,c=fc=f
15 n,m,a,b,c,d,e,f≤10100000n,m,a,b,c,d,e,f\le 10^{100000}
16
17 n,m,a,b,c,d,e,f≤101000000n,m,a,b,c,d,e,f\le 10^{1000000}
18
19
20

原题面 PDF