AC. 梦想

frank_c1

矩阵优化递推

发布于2016年03月15日 | 1条评论 | 498阅读 | 线性代数

以前一直不会独立分析有关矩阵快速幂优化递推的问题,昨天晚上自己给自己出了一道题。想了许久,似乎明白了一点,那么便记录一下吧。

首先贴上自己给自己出的题(引例):

求下列d阶线性常系数递推关系的第n0 \le n \le 10 ^ {18},将答案\mod 10 ^ 9 + 7输出。

f(x) = \sum_{i=x - d} ^ {x-1} {c_{x-i}f(i)}

如斐波那契数列f(n)=f(n-1)+f(n-2)就是一个2阶线性常系数递推关系,那我们就先解决这个特殊问题吧。

构造矩阵

\begin{bmatrix} f(x+1) \\ f(x) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(x) \\ f(x-1) \end{bmatrix}

为什么要这样构造呢?我们的目的是利用f(x)f(x-1)求出f(x+1),使得递推持续进行;同时又要保存f(x),因为后续的递推可能会用到。所以对应到上述矩阵中,就是f(x+1)=f(x)+f(x-1)f(x)保持不变。

我们将上述矩阵展开

\begin{bmatrix} f(x+1) \\ f(x) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(x-1) \\ f(x-2) \end{bmatrix} = ... = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ n\begin{bmatrix} f(1) \\ f(0) \end{bmatrix}

设转移矩阵为A,初始值矩阵为B,则最终答案为A ^ n B。运用矩阵快速幂,我们可以在O(d ^ 3 \log n)的时间求出答案。

再来探讨一下完整版的问题。我们以3阶为例,尝试模仿前面的方法构造矩阵

\begin{bmatrix} f(x+1) \\ f(x) \\ f(x-1) \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & c_3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} f(x) \\ f(x-1) \\ f(x-2) \end{bmatrix}

可以清楚地看到,上述递推完成了几个任务:使递推持续进行f(x+1) = c_1 f(x) + c_2 f(x-1) + c_3 f(x-2);保留f(x),f(x-1)的值,方便后续递推。类似地,有

\begin{bmatrix} f(x+1) \\ f(x) \\ f(x-1) \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & c_3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} ^ {n-1} \begin{bmatrix} f(2) \\ f(1) \\ f(0) \end{bmatrix}

利用这个方法,我们就可以完美地解决上述问题。

再来加强一点:

f(n)沿用上述定义,另需求出

S(n) = \sum_{i=0}^{n} {f(n)}

还要求前缀和?其实还是不难,以3阶为例,构造矩阵

\begin{bmatrix} S(x+1) \\ f(x+1) \\ f(x) \\ f(x-1) \end{bmatrix} = \begin{bmatrix} 1 & c_1 & c_2 & c_3 \\ 0 & c_1 & c_2 & c_3 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} S(x) \\ f(x) \\ f(x-1) \\ f(x-2) \end{bmatrix}

我们只需要增加一维,在递推f(n)时同步递推S(n)即可。

再来一道综合应用(其实是某模拟题):

给定n,p,m (1 \le n,p,m \le 10 ^ 9),求数列的第n

f(n) = \sum_{i=0} ^ {n} {(i+1) p ^ i} \mod m

这不是线性常系数的啊,而且也比较难直接求出递推公式,这怎么办?

一步步分解,设g(n) = (n+1) p ^ n,可以看出f(n)g(n)的前缀和。g(n)还是难以套用上面的方法,我们继续分解,设h(n) = p ^ n,此时我们可以推出h(n+1) = h(n) pg(n+1) = g(n) p + h(n+1) = g(n) p + h(n) pf(n+1) = f(n) + g(n+1) = f(n) + g(n) p + h(n) p,我们只需要同步递推3个数列即可。对于初值,有f(0)=g(0)=h(0)=1

\begin{bmatrix} f(x+1) \\ g(x+1) \\ h(x+1) \end{bmatrix} = \begin{bmatrix} 1 & p & p \\ 0 & p & p \\ 0 & 0 & p \end{bmatrix} \begin{bmatrix} f(x) \\ g(x) \\ h(x) \end{bmatrix}

最后总结一下这类问题的常用方法(仅供参考):

1.对于线性常系数齐次递推关系,可以直接求解;

2.对于求前缀和的,若能够求出原数列,我们可以增加一维前缀数列,同步递推求解。

3.构造转移矩阵时,需要注意矩阵中的系数必须是常数。如果有不是常数的,一般考虑构造辅助数列代替之。