I tried with test case Sanny provided, and the outputs are correct, however, I still got WA. Can anybody help me ? Thanks.
Code: Select all
#include <iostream>
#include <sstream>
#include <cmath>
#include <stack>
const long binaryMask[20] = {
1, // 0 2^0
2, // 1 2^1
4, // 2 2^2
8, // 3 2^3
16, // 4 2^4
32, // 5 2^5
64, // 6 2^6
128, // 7 2^7
256, // 8 2^8
512, // 9 2^9
1024, // 10 2^10
2048, // 11 2^11
4096, // 12 2^12
8192, // 13 2^13
16384, // 14 2^14
32768, // 15 2^15
65536, // 16 2^16
131072, // 17 2^17
262144, // 18 2^18
524288, // 19 2^19
};
int n;
using namespace std;
class Matrix
{
public:
Matrix();
~Matrix();
void initMatrix(bool flag);
unsigned long Cells[40][64];
// Matrix operator+(Matrix &rhs);
// Matrix operator*(Matrix &rhs);
};
struct Variant
{
Matrix Multiplier;
Matrix Adder;
bool flag;
};
Matrix sigmaMatrix;
Matrix aMatrix;
Matrix powerMatrix[20];
Matrix globalTempMatrix[21];
Matrix::Matrix(){}
Matrix::~Matrix(){}
void Matrix::initMatrix(bool flag)
{
for(int i=0;i<n; i++)
for(int j=0;j<n; j++)
Cells[i][j]=0;
if(flag==true)
for(int i=0;i<n;i++)
Cells[i][i]=1;
}
Matrix operator %(const Matrix &lhs, const int &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
C.Cells[j][kk]=lhs.Cells[j][kk]%rhs;
return C;
}
Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
int j, kk, l;
Matrix C;
C.initMatrix(false);
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
for(l=0;l<n;l++)
C.Cells[j][kk]+=lhs.Cells[j][l]*rhs.Cells[l][kk];
}
return C%10;
}
Matrix operator +(const Matrix &lhs, const Matrix &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
C.Cells[j][kk]=lhs.Cells[j][kk]+rhs.Cells[j][kk];
}
return C;
}
Matrix MatrixPower(unsigned long power)
{
Matrix temp;
unsigned long i;
temp.initMatrix(true);
for(i=0; i<20; i++)
{
if(power&binaryMask[i])
{
temp = temp * powerMatrix[i];
}
}
return temp;
}
Matrix hitung(unsigned long power, unsigned long no)
{
stack<Variant>myTree;
Variant temp;
Matrix localSigma=aMatrix;
unsigned long tempPower=power;
while(tempPower!=1)
{
// if(tempPower==1)
// {
// temp.Multiplier=aMatrix;
// temp.flag=false;
// myTree.push(temp);
// }
if(tempPower%2==0)
{
temp.Multiplier=MatrixPower(tempPower/2);
temp.flag=true;
myTree.push(temp);
}
else
{
tempPower--;
temp.Multiplier=MatrixPower(tempPower/2);
temp.Adder=MatrixPower(tempPower+1);
temp.flag=false;
myTree.push(temp);
}
tempPower/=2;
}
tempPower=1;
while(!myTree.empty())
{
temp=myTree.top();
if(temp.flag)
{
localSigma=localSigma+(temp.Multiplier*localSigma);
}
else
{
localSigma=localSigma+(temp.Multiplier*localSigma)+temp.Adder;
}
myTree.pop();
}
return localSigma;
//
// if(power==1)
// {
// return aMatrix;
// }
// else if(power%2==0)
// {
// globalTempMatrix[no]=hitung(power/2, no+1);
// return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no]);
// }
// else
// {
// power--;
// globalTempMatrix[no]=hitung(power/2, no+1);
// return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no])+MatrixPower(power+1);
// }
}
int main()
{
unsigned long k;
int i, j, kk;
n=1;
while(n!=0)
{
cin >> n >> k;
if(n!=0)
{
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
cin >> aMatrix.Cells[i][j];
}
powerMatrix[0]=aMatrix;
for(i=1;i<20;i++)
powerMatrix[i]=powerMatrix[i-1]*powerMatrix[i-1];
sigmaMatrix=hitung(k, 0);
for(j=0;j<n;j++)
{
for(kk=0; kk<n; kk++)
cout << sigmaMatrix.Cells[j][kk]%10 << " ";
cout << endl;
}
cout << endl;
}
}
}