POJ 3233 Matrix Power Series (矩阵快速等比数列求和取模)

本文主要是介绍POJ 3233 Matrix Power Series (矩阵快速等比数列求和取模)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Matrix Power Series

http://poj.org/problem?id=3233

Time Limit: 3000MS

Memory Limit: 131072K

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

题意要求矩阵S=A+A^2+A^3+...+A^k mod m，可以用二分的方法。

单个数的快速幂请参考这篇文章。
快速等比数列求和：如何求k=19的情况呢？首先根据19的二进制10011构造这么一阶差分序列：1,2,16，所以原序列是0,1,3,19.

那怎么求A+A^2+A^3+...+A^19呢？我们就按照原序列来求，也就要先求一阶差分序列。

由于第一个数是0，我们初始化ans=0

第二个数是1，ans=ans*A^1+A=A

第三个数是3，ans=ans*A^2+A(I+A)=A+A^2+A^3

由于二进制中间有两个0，所以与ans相乘的数变为A^16(算法：A^2*A^2=A^4，A^4*A^4=A^16)

与ans*A^16相加的数变为A+...A^16(算法：(A+A^2)*((I+A^2)=A+...+A^4,(A+...+A^4)*(I+A^4)=A+...+A^8,(A+...+A^8)*(I+A^8)=A+...A^16)

第四个数是19，ans=ans*A^16+(A+...A^16)

完整代码：

/*79ms,144KB*/#include <cstdio>
#include <cstring>
const int matSize = 31;int calSize = matSize, mod = 1000000007;struct Matrix
{int val[matSize][matSize];Matrix(bool Init = false)///使用默认实参以减少代码量{for (int i = 0; i < calSize; i++){for (int j = 0; j < calSize; j++)val[i][j] = 0;if (Init)val[i][i] = 1;///单位矩阵}}void print(){for (int i = 0; i < calSize; i++){for (int j = 0; j < calSize; j++){if (j)putchar(' ');printf("%d", val[i][j]);}puts("");}}
} Base;Matrix operator + (Matrix &_a, Matrix &_b)
{Matrix ret;for (int i = 0; i < calSize; i++)for (int j = 0; j < calSize; j++)ret.val[i][j] = (_a.val[i][j] + _b.val[i][j]) % mod;return ret;
}Matrix operator * (Matrix &_a, Matrix &_b)
{Matrix ret = Matrix();for (int i = 0; i < calSize; i++)for (int k = 0; k < calSize; k++)if (_a.val[i][k])///优化一下for (int j = 0; j < calSize; j++){ret.val[i][j] += _a.val[i][k] * _b.val[k][j];ret.val[i][j] %= mod;}return ret;
}void deal(int k)
{Matrix one = Matrix(true), ans = Matrix();Matrix ep = Base, tmp = Base, temp;while (k){if (k & 1){ans = ans * ep;ans = ans + tmp;}temp = one + ep;tmp = tmp * temp;ep = ep * ep;k >>= 1;}ans.print();
}int main()
{int k;while (~scanf("%d%d%d", &calSize, &k, &mod)){for (int i = 0; i < calSize; i++)for (int j = 0; j < calSize; j++){scanf("%d", &Base.val[i][j]);Base.val[i][j] %= mod;}deal(k);}return 0;
}

这篇关于POJ 3233 Matrix Power Series (矩阵快速等比数列求和取模)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！