APTX Blog

A Moe Blog Set By APTX

POJ 3233 Matrix Power Series(矩阵快速幂+二分)题解

洛谷:https://www.luogu.org/problemnew/show/U50124

Description

给定一个 n*n 的矩阵 A 以及一个正整数 k,计算\(S = A^1 + A^2 + A^3+…+A^k\)

Input

输入只有一组测试数据。输入的第一行包括三个正整数 nkm。接下来的 n 行每行包括 n 个非负整数,按照行优先的顺序输入矩阵 A 的元素。

Output

输出 S 中每一个元素 mod(%)m 以后的值

Sample Input

Sample Output

解析及代码

暴力:

我们考虑暴力解法,根据题意模拟,每次令i从1枚举到k,矩阵快速幂求解\(power(A,i)\),进行矩阵加法将\(power(A,i)\)累加起来。我觉得复杂度是\(O(k(n^3logn + n^2))\)的,反正肯定过不了。

正解:

考虑分类讨论,将k分为奇数和偶数进行分类讨论,对于k为偶数的情况,我们可以推出如下规律(例如k为6)

\(S(6)=A^1+A^2+A^3+A^4+A^5+A^6\)

\(=A^1+A^2+A^3+A^3*(A+A^2+A^3)\)

\(=S(3)*(1 + A^3)\)

所以当k为偶数时,就有:\(S(k)=S(k/2)*(1+A^\frac{k}{2})\)

那么当k为奇数时,显然有:\(S(k)=S(k-1)+A^k\)

根据以上规律,二分进行求解 复杂度不知道多少,反正是:\(O(AC)\)

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注