题目描述

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的$n$行$m$列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质：若用$F_{i,j}$来表示矩阵中第$i$行第$j$列的元素，则$F_{i,j}$满足下面的递推式:

$$\begin{aligned} F_{1,1} &= 1 \\ F_{i,j} &= aF_{i,j-1} + b \; (j \neq 1) \\ F_{i,1} &= cF_{i-1,m} + d \; (i \neq 1) \end{aligned}$$

递推式中$a,b,c,d$都是给定的常数。

现在婷婷想知道$F_{n,m}$的值是多少，请你帮助她。

由于最终结果可能很大，你只需要输出$F_{n,m}$除以$1,000,000,007$的余数。

输入格式

一行有六个整数$n,m,a,b,c,d$。意义如题所述。

输出格式

包含一个整数，表示$F_{n,m}$除以$1,000,000,007$的余数。

题目解析

考虑若知道$F_{i,1}$，怎样$O(1)$求出$F_{i,m}$。

根据前一个递推式$F_{i,j} = aF_{i,j-1} + b$，有

$$F_{i,m} = a ^ {m-1}F_{i,1} + b \sum_{i=0} ^ {m-2} {a ^ i}$$

根据后一个递推式，有

$$F_{i+1,1} = cF_{i,m} + d = a ^ {m-1} c F_{i,1} + bc \sum_{i=0} ^ {m-2} {a ^ i} + d$$

观察上述递推式，可以发现唯一有些麻烦的是$\sum_{i=0} ^ {m-2} {a ^ i}$。可以用等比数列求和公式，也可以矩阵快速幂。我采用矩阵快速幂$O(\log m)$求。设$A = a ^ {m-1} c, B = bc \sum_{i=0} ^ {m-2} {a ^ i} + d$，则有$F_{i+1,1} = AF_{i,1} + B$，$O(\log n)$矩阵快速幂即可求得$F_{n,1}$，再通过上述递推式即可求得$F_{n,m}$。

时间复杂度$O(\log n + \log m)$。

值得注意的是，本题中因为指数较大，转成二进制复杂度太高。可以直接用十进制快速幂解决。具体思想和二进制快速幂是一样的，常数略大，需要适当优化。