Submission #9789200

---

Source Code Expand

#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map> 
#include<vector>
#include<queue>
#include<set>

#include<deque> 
#include<bitset>
#include<string>
#define N 40
#define K 300005
#define MOD 1e9+7
#define int long long 
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
int n;



int mod = 1e9 + 7;

vector<vector<int>> pro(vector<vector<int>> mat1, vector<vector<int>> mat2){
	vector<vector<int>>ans(n, vector<int>(n,0));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int t = 0;
			for(int k = 0; k<n;k++){
				t += (mat1[i][k] * mat2[k][j]);
				if(t >= mod)
					t %= mod;
			}
			ans[i][j] = t;
		}
	}
	return ans;
}
				

vector<vector<int>> solve(vector<vector<int>> mat, int p){
	if(p == 1){
		return mat;
	}
	vector<vector<int>>temp(n, vector<int>(n));
    vector<vector<int>>ans(n, vector<int>(n));
	temp = solve(mat, p/2);
	ans = pro(temp, temp);
	if(p %2 == 0)
		return ans;
	else
		return pro(ans, mat);
}
	

int32_t main(){
	int k;
	cin>>n>>k;
    if(n == 1){
        cout<<0;
        return 0;
    }
	vector<vector<int>>a(n, vector<int>(n));
	vector<int>col(n);
	

		
	for(int i=0;i<n;i++){
		int o = 0;
		for(int j=0;j<n;j++){
			cin>>a[i][j];
			o += a[i][j];
		}
		col[i] = o;
	}
	vector<vector<int>>res(n, vector<int>(n));
	res = solve(a,  k-1);

	int for_each[n];
    
	for(int i=0;i<n;i++){
		for_each[i] = 0;
		int t = 0;
		for(int j = 0; j<n; j++){
			t += (res[i][j] * col[j]);
			if(t >= mod)
				t %= mod;
		}
		for_each[i] = t;
	}
	int ans = 0;
	for(int i=0;i<n;i++){
		ans += for_each[i];
		if(ans >= mod)
			ans -= mod;
	}
	cout<<ans<<endl;
		
	
	
}

Submission Info

Test Cases