题解 UVA11149 【Power of Matrix】

Nathaly · 2021-01-25 09:43:30 · 题解

UVA11149 题解

思路

提供另一种 O(Tn^3\log k) 的做法。

首先，对于单组数锯，十分显然地有一种 O(n^3 \log^2k) 的做法：

设 Solve(Matrix &x,int k) 代表 x=A+A^2+\dots +A^k。那么当 k 为奇数时，递归调用 Solve(z,k-1)，z 为一个临时矩阵。此时 x=A+Az。当 k 为偶数时，递归调用 Solve(z,k/2)，则 x=z+A^{\frac{k}{2}}z。用矩阵快速幂算 A^{\frac{k}{2}} 即可。

发现这个 Solve 的过程可以顺便算快速幂。再带一个参数 Matrix &pre，表示 A^k 即可，然后对于奇偶分类讨论。

代码（10ms）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
inline bool chkmax(T &i,const T&j){return i<j?(i=j,1):0;}
template<typename T>
inline bool chkmin(T &i,const T&j){return i>j?(i=j,1):0;}
#define ll long long
#define INF 0x3f3f3f3f
#define N 41
#define MOD 10
typedef int Mat[N][N];
int n,k;Mat a,buf;//buf 是临时数组，没用
void MatAdd(Mat &res,const Mat &a,const Mat &b){//res=a+b
    static Mat c;memset(c,0,sizeof c);
    For(i,1,n) For(j,1,n){
        c[i][j]=(a[i][j]+b[i][j])%MOD;
    }
    memcpy(res,c,sizeof c);
}
void MatMul(Mat &res,const Mat &a,const Mat &b){//res=a*b
    static Mat c;memset(c,0,sizeof c);
    For(i,1,n) For(k,1,n) if(a[i][k]) For(j,1,n){
        c[i][j]+=a[i][k]*b[k][j];c[i][j]%=MOD;
    }
    memcpy(res,c,sizeof c);
}
void MatPow(Mat &res,const Mat &x,int b){//这个用不着
    static Mat a;memcpy(a,x,sizeof x);
    memset(res,0,sizeof res);For(i,1,n) res[i][i]=1;
    while(b){
        if(b&1) MatMul(res,res,a);
        b>>=1;MatMul(a,a,a);
    }
}
void Solve(Mat &ans,int k,Mat &pre){
    if(k==1){
        memcpy(ans,a,sizeof a);
        memcpy(pre,a,sizeof a);//当 k=1 时，上次调用它的一定是 2k，那么 pre=A^{2k/2}=A
        return;
    }
    Mat z,temp;
    if(k&1){
        Solve(z,k-1,temp);//z=Solve(k-1),temp=a^(k-1)
        MatMul(pre,a,temp);//pre=temp*a=a^k
        MatMul(temp,a,z);//temp=a*z=a*Solve(k-1)=a*(a+a^2+...+a^(k-1))=a^2+a^3+...+a^k
        MatAdd(ans,a,temp);//ans=a+temp=a+a^2+...+a^k
    }else{
        Solve(z,k>>1,temp);//z=Solve(k/2),temp=a^(k/2)
        //MatPow(temp,a,k>>1);
        MatMul(pre,temp,temp);//pre=temp^2=a^k
        MatMul(temp,temp,z);//buf=temp*Solve(k/2)=a^(k/2+1)+...+a^k
        MatAdd(ans,z,temp);//ans=z+buf=a+...+a^k
    }
}
int Work(){
    if(scanf("%d %d",&n,&k)==EOF||n==0) return 1;
    memset(a,0,sizeof a);
    For(i,1,n){
        For(j,1,n){
            scanf("%d",&a[i][j]);
            a[i][j]%=MOD;//这里如果不取模似乎会 WA
        }
    }
    Mat ans;
    Solve(ans,k,buf);
    For(i,1,n){
        For(j,1,n-1){
            printf("%d ",ans[i][j]);
        }
        printf("%d",ans[i][n]);
        puts("");
    }
    puts("");
    return 0;
}
int main(){
    //freopen("UVA11149.in","r",stdin);
    //freopen("UVA11149.out","w",stdout);
    while(!Work());
    return 0;
}