Submission #3952105

---

Source Code Expand

//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define leadzero(a) __builtin_clz(a) // count leading zeroes
#define trailzero(a) __builtin_ctz(a) // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln endl
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it<<ln;} cerr<<endl
#define dbgstlp32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cerr<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inp freopen("input.txt", "r", stdin)
#define outp freopen("output.txt", "w", stdout)
#define dbgm(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
typedef long long int  ll;
typedef long double  ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM = 2e5+5, MOD = 1e9+7, EPS = 1e-9;
int t,n,m,k,x,y;


const int MAX_N = 50; // Fibonacci matrix, increase/decrease this value as needed

struct Matrix { ll mat[MAX_N][MAX_N]; }; // we will return a 2D array

Matrix matMul(Matrix a, Matrix b) {
	Matrix ans; int i, j, k;
	for (i = 0; i < MAX_N; i++)
	for (j = 0; j < MAX_N; j++)
	for (ans.mat[i][j] = k = 0; k < MAX_N; k++){
		ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
		ans.mat[i][j]%=MOD;
	}
	return ans; 
}

// if necessary, use modulo arithmetic

Matrix matPow(Matrix base, ll p) {
	// O(n^3 log p)
	Matrix ans; int i, j;
	for (i = 0; i < MAX_N; i++) for (j = 0; j < MAX_N; j++) 
	ans.mat[i][j] = (i == j); // prepare identity matrix
	while (p) {
		// iterative version of Divide & Conquer exponentiation
		if (p & 1) ans = matMul(ans, base);	// if p is odd (last bit is on)
		base = matMul(base, base);	// square the base
		p >>= 1;
		// divide p by 2
	}
	return ans; 
}



int main(){
	fastio;
	ll n,k;
	cin>>n>>k;
	Matrix m;
	forn(i,n){
		forn(j,n){
			cin>>m.mat[i][j];
		}
	}
	Matrix p = matPow(m,k);
	ll ans=0;
	forn(i,n){
		forn(j,n){
			ans+=p.mat[i][j];
		}
	}
	ans%=MOD;
	cout<<ans<<ln;
	return 0;
}

Submission Info

Judge Result