P3390

Aryper · 2021-07-30 18:58:06 · 个人记录

【模板】矩阵快速幂

ans 矩阵的初值可以直接赋为 a 矩阵，然后把 k 减一即可。

时间复杂度 O(n^3\log k) 。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=5e2,mo=1e9+7;

ll n,k;

ll a[N+5][N+5],ans[N+5][N+5],c[N+5][N+5];

void mul() {
    memset(c,0,sizeof(c));
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            for(ll k=1;k<=n;k++) {
                c[i][j]=(c[i][j]+ans[i][k]*a[k][j]%mo)%mo;
            }
        }
    }
    memcpy(ans,c,sizeof(c));
}

void mulself() {
    memset(c,0,sizeof(c));
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            for(ll k=1;k<=n;k++) {
                c[i][j]=(c[i][j]+a[i][k]*a[k][j]%mo)%mo;
            }
        }
    }
    memcpy(a,c,sizeof(c));
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();k=read();

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            a[i][j]=ans[i][j]=read();
        }
    }

    k--;

    while(k>0) {
        if(k&1) mul();
        mulself();k>>=1;
    }

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            write(ans[i][j]);putchar(' ');
        }
        putchar('\n');
    }

    return 0;
}