uva11149

Consider an n-by-n matrix A. We define Ak = A ∗ A ∗ . . . ∗ A (k times). Here, ∗ denotes the usual matrix multiplication. You are to write a program that computes the matrix A + A2 + A3 + . . . + Ak . Example Suppose A =   0 2 0 0 0 2 0 0 0  . Then A2 =   0 2 0 0 0 2 0 0 0     0 2 0 0 0 2 0 0 0   =   0 0 4 0 0 0 0 0 0  , thus: A + A2 =   0 2 0 0 0 2 0 0 0   +   0 0 4 0 0 2 0 0 0   =   0 2 4 0 0 2 0 0 0   Such computation has various applications. For instance, the above example actually counts all the paths in the following graph: Input Input consists of no more than 20 test cases. The first line for each case contains two positive integers n (≤ 40) and k (≤ 1000000). This is followed by n lines, each containing n non-negative integers, giving the matrix A. Input is terminated by a case where n = 0. This case need NOT be processed. Output For each case, your program should compute the matrix A + A2 + A3 + . . . + Ak . Since the values may be very large, you only need to print their last digit. Print a blank line after each case. Sample Input 3 2 0 2 0 0 0 2 0 0 0 0 0 Sample Output 0 2 4 0 0 2 0 0 0

矩阵快速幂+分治。。。

很巧妙啊先开始还在想怎么错位相减。。。

具体细节不讲了代码里都有这道题给我们的启示是碰见这种连续幂相加的东西要想分治。。。

先开始t了半天，结果写成暴力了。。。

#include<bits/stdc++.h>

using namespace std;

const int N = ;

struct mat {

    int a[N][N];

} A;

int n, k;

mat operator * (mat A, mat B)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= n; ++j)

             for(int k = ; k <= n; ++k) ret.a[i][j] = (ret.a[i][j] + A.a[i][k] %  * B.a[k][j] % ) % ;

    return ret;

}

mat power(mat x, int t)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

    for(int i = ; i <= n; ++i) ret.a[i][i] = ;

    for(; t; t >>= , x = x * x) if(t & ) ret = ret * x;

    return ret;

}

mat operator + (mat A, mat B)

{

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= n; ++j) A.a[i][j] = (A.a[i][j] + B.a[i][j]) % ;

    return A;

}

mat solve(int t)

{

    if(t == ) return A;

    mat x = solve(t / ), ret = x, B = power(A, t / );

    if(t & ) return x + (x + B * A) * B;

    else return x + x * B;

}

int main()

{

    while(scanf("%d%d", &n, &k))

    {

        if(n == ) break;

        for(int i = ; i <= n; ++i)

            for(int j = ; j <= n; ++j) scanf("%d", &A.a[i][j]), A.a[i][j] %= ;

        mat x = solve(k);

        for(int i = ; i <= n; ++i)

        {

            for(int j = ; j < n; ++j) printf("%d ", x.a[i][j]);

            printf("%d\n", x.a[i][n]);

        }

        puts("");

    }

    return ;

}

巴特西

uva11149

最新文章

热门文章