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