Untitled
#include<bits/stdc++.h> using namespace std; typedef long long ll ; typedef vector<vector<ll>> Matrix; #define int long long int MAX_N; ll MOD=1e9+7; ll mod(ll x,ll y) { return (x)%MOD; } Matrix matMul(Matrix a, Matrix b) { // normally O(n^3) Matrix ans(MAX_N,vector<ll>(MAX_N)); // but O(1) as n = 2 for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < MAX_N; ++j) ans[i][j] = 0; for (int i = 0; i < MAX_N; ++i) for (int k = 0; k < MAX_N; ++k) { if (a[i][k] == 0) continue; // optimization for (int j = 0; j < MAX_N; ++j) { ans[i][j] += mod(a[i][k], MOD) * mod(b[k][j], MOD); ans[i][j] = mod(ans[i][j], MOD); // modular arithmetic } } return ans; } Matrix matPow(Matrix base, int p) { Matrix ans(MAX_N,vector<ll>(MAX_N)); for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < MAX_N; ++j) ans[i][j] = (i == j); while (p) { if (p&1) ans = matMul(ans, base); base = matMul(base, base); p >>= 1; } return ans; } signed main() { int n,k; cin>>n>>k; MAX_N=n; Matrix v(n,vector<ll>(n)); for (int i=0;i<n;i++) { for (int j=0;j<n;j++) cin>>v[i][j]; } Matrix ans=matPow(v,k); ll output=0; for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { output+=ans[i][j]; output%=MOD; } } cout<<output; }
Leave a Comment