单位矩阵相当于普通乘法算术中的单位元.
代码如下
- #include <bits/stdc++.h>
- #define pb push_back
- #define mp make_pair
- #define all(x) x.begin(),x.end()
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> P;
- const int mod=1e9+7;
- const int inf=0x3f3f3f3f;
- const int maxn=101;
- inline ll read(){
- ll x=0,f=1;char ch;
- do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
- do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
- return f*x;
- }
- int n;ll m;
- ll c[maxn][maxn],ans[maxn][maxn],res[maxn][maxn];
- void mul(ll a[][maxn],ll b[][maxn]){
- memset(res,0,sizeof(res));
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- res[i][j]=(res[i][j]+a[i][k]*b[k][j]%mod)%mod;
- memcpy(a,res,sizeof(res));
- }
- void read_and_parse(){
- n=read(),m=read();
- for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=read();
- for(int i=1;i<=n;i++)ans[i][i]=1;
- }
- void solve(){
- for(;m;m>>=1,mul(c,c))if(m&1)mul(ans,c);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++)printf("%lld",ans[i][j]);
- puts("");
- }
- }
- int main(){
- read_and_parse();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3003252.html