Artifact 2c92483914a46a5636fc57fdf4c53f62bfa9fd8e

• File _lib/numeric/matrix.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/numeric/matrix.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// Matrix Operations
//
// Verified by
//   - SRM342 Div1 LV3
//   - SRM341 Div1 LV3
//   - SRM338 Div1 LV2
//-------------------------------------------------------------

vector<LL> vMul( const vector< vector<LL> >& A, const vector<LL>& B )
{
	const int n = A.size();

	vector<LL> C(n);
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			C[i] += A[i][j] * B[j];
	return C;
}

vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
{
	const int n = A.size();

	vector< vector<LL> > C(n, vector<LL>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j) {
			LL Cij = 0;
			for(int k=0; k<n; ++k)
				Cij += A[i][k] * B[k][j];
			C[i][j] = Cij;
		}
	return C;
}

vector< vector<LL> > mPow( vector< vector<LL> > M, LL t ) // t>0
{
	vector< vector<LL> > R;
	for(; t; t>>=1, M=mMul(M,M))
		if( t&1 )
			R = (R.empty() ? M : mMul(R,M));
	return R;
}

vector< vector<LL> > mAdd( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
{
	const int n = A.size();

	vector< vector<LL> > C(n, vector<LL>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			C[i][j] = A[i][j] + B[i][j];
	return C;
}