ACM-数论-矩阵快速幂 POJ3233 矩阵快速幂

这里是题面

这个是写得最好的题解

下次再来补坑

注意一点：矩阵开long long 会超时，矩阵必须开到60+,不然会RE

#include<iostream>
#include<cstdio> 
#include<string.h>
using namespace std;
typedef long long ll;
int g;
int mod;
struct mx{
    int v[][];//ll会超时%因为取模，所以不需要ll 
}a;
mx mul(mx a,mx t,int g){
    mx res;
    memset(res.v,,sizeof(res.v));
    for(int i=;i<g;i++){
        for(int j=;j<g;j++){
            for(int k=;k<g;k++){
                res.v[i][j]+=(a.v[i][k]%mod)*(t.v[k][j]%mod)%mod;
                res.v[i][j]%=mod;
            } 
        }
    }
    return res;
}
mx power(mx a,ll b,int g){
    mx ans;
    memset(ans.v,,sizeof(ans.v));
    for(int i=;i<g;i++)ans.v[i][i]=;
    while(b>){
        if(b&)ans=mul(ans,a,g);
        b=b>>;
        a=mul(a,a,g);
    }
    return ans;
}
int main(){
    int n;
    ll k;
    while(scanf("%d%lld%d",&n,&k,&mod)==){
        g=n*;
        memset(a.v,,sizeof(a.v));
        int i,j;
        for(i=;i<g;i++){
            for(j=;j<n;j++){
                if(i<n)scanf("%d",&a.v[i][j]);
            }
            if(i<n)a.v[i][i+n]=;
            else a.v[i][i]=;
        }
        /*for(int i=0;i<g;i++){
            for(int j=0;j<g;j++)cout<<a.v[i][j]<<" ";
            cout<<endl;
        }*/
        mx m=power(a,k+,g);
        for(i=;i<n;i++){
            for(j=n;j<g;j++){
                if(j==i+n)m.v[i][j]=(m.v[i][j]-+mod)%mod;
                printf("%d",m.v[i][j]);//cout<<;
                if(j<g-)printf(" ");
            }
            printf("\n");//cout<<endl;
        }
    }
    return ;
}