求调矩阵快速幂
  • 板块学术版
  • 楼主Chancylaser
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/5/2 10:30
  • 上次更新2023/11/4 23:51:49
查看原帖
求调矩阵快速幂
241817
Chancylaser楼主2021/5/2 10:30

不说了,快调崩溃了,求大佬解答 代码:




#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k;
struct jv{
    int n,m;
    int z[233][233];
    jv(){
        n=0,m=0;
        memset(z,0,sizeof(z));
    } 
};
jv operator*(const jv &m1,const jv &m2){     
    jv m3;
    m3.n=m1.n;
    m3.m=m2.m;
    for(int i=1;i<=m3.n;i++)
        for(int j=1;j<=m3.m;j++)
            for(int k=1;k<=m1.m;k++)
                m3.z[i][j]+=m1.z[i][k]*m2.z[k][j];
    return m3;
}
typedef long long ll;
jv qp(jv &x,ll nd){
    jv res;
    memset(res.z,0,sizeof(res.z));
    res.n=n;
    res.m=n;
    for(int i=1;i<=n;i++)
        res.z[i][i]=1;
    while(nd>0){
        if(nd&1)    res=res*x;
        x=x*x;
        nd>>=1;
    }
    return res;
}
int main(){
    cin>>n>>k;
    jv a;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a.z[i][j];
    jv b=qp(a,k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<b.z[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

2021/5/2 10:30
加载中...