程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3233 Matrix Power Series(矩陣+二分)

POJ 3233 Matrix Power Series(矩陣+二分)

編輯：C++入門知識

POJ 3233 Matrix Power Series(矩陣+二分)

題目大意：求由矩陣 A構成的矩陣 S = A + A^2 + A^3 + … + A^k。k的取值范圍是：10^9數據很大，應該二分。

對於一個k來說，s(k) = (1+A^(k/2)) *( A+A^2+……+A^(k/2))。如果k為奇數的話需要加上A^(k/2 + 1)。

所以二分求和，復雜度就降下來了，當然還得用到矩陣快速冪。

Matrix Power Series Time Limit: 3000MS Memory Limit: 131072K Total Submissions: 15477 Accepted: 6621

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 nnonnegative 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

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-10
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)>= 1;
    }
    return s;
}

matrix Add(matrix a,matrix b, int n)  ///矩陣加法
{
    matrix c;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            c.f[i][j] = a.f[i][j]+b.f[i][j];
            c.f[i][j] %= mod;
        }
    }
    return c;
}

matrix Matrix_Sum(matrix a, int k, int n)
{
    if(k == 1) return a;
    matrix dx,dy;
    dx = Matrix_Sum(a, k/2, n);///二分，遞歸；
    if(k&1)
    {
        dy = pow_mod(a, k/2+1, n);
        dx = Add(dx, mul(dx, dy, n), n);
        dx = Add(dy,dx, n);
    }
    else 
    {
        dy = pow_mod(a, k/2, n);
        dx = Add(dx,mul(dx, dy, n), n);
    }
    return dx;
}

int main()
{
    int n, k;
    while(cin >>n>>k>>mod)
    {
        matrix c;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                scanf("%d",&c.f[i][j]);
                c.f[i][j] %= mod;
            }
        }
        matrix d = Matrix_Sum(c, k, n);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n-1; j++) cout<