I am getting WA for my following solution for problem MPOW. I have used long long int
but no better outcome…
#include <iostream>
#define ll long long
#define mod 1000000007
#define M 101
using namespace std;
ll arr[M][M], I[M][M];
void multiply(ll (&A)[M][M], ll (&B)[M][M], int dim){
// Temporary matrix to store the result
int res[dim+1][dim+1];
for(int i = 1; i<=dim; i++){
for(int j = 1; j<=dim; j++){
res[i][j] = 0;
for(int k = 1; k <=dim; k++){
res[i][j] = res[i][j]% mod + (((A[i][k])%mod) * ((B[k][j])%mod))%mod;
}
}
}
// copy the result into I matrix
for(int i = 1; i <= dim; i++){
for(int j = 1; j <= dim; j++){
B[i][j] = res[i][j];
}
}
}
void power(int dim, int n){
// initializing the identity matrix
for(int i = 1; i <=dim; i++){
for(int j = 1; j <=dim; j++){
if(i == j) I[i][j] = 1;
else I[i][j] = 0;
}
}
// calculating the answer
while(n){
if(n%2){
multiply(arr, I, dim), n--;
}else{
multiply(arr, arr, dim), n/=2;
}
}
// storing the answer back into the matrix
for(int i = 1; i <= dim; i++){
for(int j = 1; j <= dim; j++){
arr[i][j] = I[i][j];
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
int m, n;
cin >> m >> n;
for(int i = 1; i <=m; i++){
for(int j = 1; j <=m; j++){
cin >> arr[i][j];
}
}
power(m, n);
// printing the answer
for(int i = 1; i <=m; i++){
for(int j = 1; j<=m; j++){
cout << arr[i][j] << " ";
}
cout << endl;
}
}
return 0;
}