Artifact Content
Not logged in

Artifact ba1b2d78835ef59e8248b4cd7a56522db538b766


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

template<typename T>
vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v)
{
	int N = a.size();
	vector<T> u(N);
	for(int i=0; i<N; ++i)
	for(int j=0; j<N; ++j)
		u[i] += a[i][j]*v[j];
	return u;
}

template<typename T>
vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b)
{
	int N = a.size();
	vector< vector<T> > c(N, vector<T>(N));
	for(int i=0; i<N; ++i)
	for(int j=0; j<N; ++j)
	for(int k=0; k<N; ++k)
		c[i][j] += a[i][k]*b[k][j];
	return c;
}

template<typename T>
vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v)
{
	for(; e; e>>=1, a=MATMUL(a,a))
		if(e&1)
			v = MATMUL(a, v);
	return v;
}

template<typename T>
vector< vector<T> > MATPOW(vector< vector<T> > a, LL e)
{
	int N = a.size();
	vector< vector<T> > c(N, vector<T>(N));
	for(int i=0; i<N; ++i) c[i][i] = 1;
	for(; e; e>>=1) {
		if(e&1)
			c = MATMUL(c, a);
		a = MATMUL(a, a);
	}
	return c;
}

/****************************************************************************
   NOTES ON THE USAGE
 ****************************************************************************

A[to][from] = #transition
--------------------------------------------

     frm
   (. . .) (q0)
to (. . .) (q1)
   (. . .) (q2)



 qi
--------------------------------------------

     frm
   (. . . 0) (.)
to (. . . 0) (.)
   (. . . 0) (.)
   (0 1 0 1) (0)
      ^
      i
Then,
  q[i]@0                 = (A^1 v)[$-1]
  q[i]@0 + q[i]@1        = (A^2 v)[$-1]
  q[i]@0 + ... + q[i]@k  = (A^(k+1) v)[$-1]



 q_all
--------------------------------------------

     frm
   (. . . 0) (.)
to (. . . 0) (.)
   (. . . 0) (.)
   (1 1 1 1) (0)

Then,
  q @0                 = (A^1 v)[$-1]
  q @0 + ... + q @k  = (A^(k+1) v)[$-1]





Application: x^0 + x^1 + ... + x^e-1
--------------------------------------------

  (x 0)^e (1)  = (x^e                    )
  (1 1)   (0)    (x^0 + x^1 + ... + x^e-1)



Application: e x^0 + (e-1) x^1 + ... + 1 x^e-1
--------------------------------------------

  (x 0 0)^e (x)  = (x^e+1                                       )
  (1 1 0)   (1)    (x^0 + x^1 + ... + x^e                       )
  (0 1 1)   (0)    ( of  = e x^0 + (e-1) x^1 + ... + 1 x^e-1)
*/