23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Matrix Operations
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM342 Div1 LV3
23dfcca431 2011-02-23        kinaba: //   - SRM341 Div1 LV3
23dfcca431 2011-02-23        kinaba: //   - SRM338 Div1 LV2
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: vector<LL> vMul( const vector< vector<LL> >& A, const vector<LL>& B )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	const int n = A.size();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector<LL> C(n);
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<n; ++i)
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<n; ++j)
23dfcca431 2011-02-23        kinaba: 			C[i] += A[i][j] * B[j];
23dfcca431 2011-02-23        kinaba: 	return C;
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	const int n = A.size();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector< vector<LL> > C(n, vector<LL>(n));
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<n; ++i)
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<n; ++j) {
23dfcca431 2011-02-23        kinaba: 			LL Cij = 0;
23dfcca431 2011-02-23        kinaba: 			for(int k=0; k<n; ++k)
23dfcca431 2011-02-23        kinaba: 				Cij += A[i][k] * B[k][j];
23dfcca431 2011-02-23        kinaba: 			C[i][j] = Cij;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 	return C;
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: vector< vector<LL> > mPow( vector< vector<LL> > M, LL t ) // t>0
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	vector< vector<LL> > R;
23dfcca431 2011-02-23        kinaba: 	for(; t; t>>=1, M=mMul(M,M))
23dfcca431 2011-02-23        kinaba: 		if( t&1 )
23dfcca431 2011-02-23        kinaba: 			R = (R.empty() ? M : mMul(R,M));
23dfcca431 2011-02-23        kinaba: 	return R;
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: vector< vector<LL> > mAdd( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	const int n = A.size();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector< vector<LL> > C(n, vector<LL>(n));
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<n; ++i)
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<n; ++j)
23dfcca431 2011-02-23        kinaba: 			C[i][j] = A[i][j] + B[i][j];
23dfcca431 2011-02-23        kinaba: 	return C;
23dfcca431 2011-02-23        kinaba: }