首页 > 其他 > 详细

POJ3233 Matrix Power Series

时间:2019-04-03 18:31:55      阅读:124      评论:0      收藏:0      [点我收藏+]

题意

Language:
Matrix Power Series
Time Limit: 3000MSMemory Limit: 131072K
Total Submissions: 29541Accepted: 11975

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). 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

Source

POJ Monthly--2007.06.03, Huang, Jinsong

分析

跟整数的分治差不多。
\[ \sum_{i=1}^kA^i=\left\{\begin{array}{} (I+A^{k/2})\sum_{i=1}^{k/2}A^i&,&k\equiv 0\ (\bmod 2) \A+(A+A^{(k+1)/2})\sum_{i=1}^{(k-1)/2}A^i&,&k\equiv 1\ (\bmod 2) \end{array}\right. \]
时间复杂度\(O(n^3 \log k)\)

代码

#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=30;
struct M{int a[N][N];};
int n,k,m;
M add(co M&x,co M&y){
    M ans;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)    
        ans.a[i][j]=(x.a[i][j]+y.a[i][j])%m;
    return ans;
}
M mul(co M&x,co M&y){
    static M ans;
    memset(ans.a,0,sizeof ans.a);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            for(int k=0;k<n;++k)
                ans.a[i][j]=(x.a[i][k]*y.a[k][j]%m+ans.a[i][j])%m;
    return ans;
}
M ksm(M x,int k){
    static M ans;
    memset(ans.a,0,sizeof ans.a);
    for(int i=0;i<n;++i) ans.a[i][i]=1;
    for(;k;x=mul(x,x),k>>=1)
        if(k&1) ans=mul(ans,x);
    return ans;
}
M get(co M&x,int k){
    if(k==1) return x;
    M y=ksm(x,(k+1)>>1);
    M z=get(x,k>>1);
    return k&1?add(x,mul(add(x,y),z)):mul(add(ksm(x,0),y),z);
}
int main(){
//  freopen(".in","r",stdin),freopen(".out","w",stdout);
    M x;
    read(n),read(k),read(m);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j) x.a[i][j]=read<int>()%m;
    x=get(x,k);
    for(int i=0;i<n;++i,puts(""))
        for(int j=0;j<n;++j) printf("%d ",x.a[i][j]);
    return 0;
}

POJ3233 Matrix Power Series

原文:https://www.cnblogs.com/autoint/p/10650669.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!