AC. 梦想

frank_c1

[NOI 2013] 矩阵游戏

发布于2016年05月03日 | 暂无评论 | 540阅读 | 线性代数

题目描述

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的nm列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用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} + BO(\log n)矩阵快速幂即可求得F_{n,1},再通过上述递推式即可求得F_{n,m}

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

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