Submission #3952105

Source Code Expand

Copy
//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

Submission Time
Task R - Walk
User TheOneYouWant
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3224 Byte
Status
Exec Time 57 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 3 ms 384 KB
0_01 3 ms 384 KB
0_02 3 ms 384 KB
0_03 2 ms 384 KB
0_04 41 ms 384 KB
1_00 2 ms 384 KB
1_01 41 ms 384 KB
1_02 3 ms 384 KB
1_03 41 ms 384 KB
1_04 2 ms 384 KB
1_05 41 ms 384 KB
1_06 2 ms 384 KB
1_07 57 ms 384 KB
1_08 30 ms 384 KB
1_09 41 ms 384 KB
1_10 45 ms 384 KB
1_11 41 ms 384 KB
1_12 45 ms 384 KB
1_13 47 ms 384 KB
1_14 46 ms 384 KB
1_15 44 ms 384 KB
1_16 45 ms 384 KB
1_17 44 ms 384 KB