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)
*/