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: 7d2fe88cb2 2012-09-08 kinaba: template<typename T> 7d2fe88cb2 2012-09-08 kinaba: vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) 7d2fe88cb2 2012-09-08 kinaba: { 7d2fe88cb2 2012-09-08 kinaba: int N = a.size(); 7d2fe88cb2 2012-09-08 kinaba: vector<T> u(N); 7d2fe88cb2 2012-09-08 kinaba: for(int i=0; i<N; ++i) 7d2fe88cb2 2012-09-08 kinaba: for(int j=0; j<N; ++j) 7d2fe88cb2 2012-09-08 kinaba: u[i] += a[i][j]*v[j]; 7d2fe88cb2 2012-09-08 kinaba: return u; 7d2fe88cb2 2012-09-08 kinaba: } 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: template<typename T> 7d2fe88cb2 2012-09-08 kinaba: vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b) 7d2fe88cb2 2012-09-08 kinaba: { 7d2fe88cb2 2012-09-08 kinaba: int N = a.size(); 7d2fe88cb2 2012-09-08 kinaba: vector< vector<T> > c(N, vector<T>(N)); 7d2fe88cb2 2012-09-08 kinaba: for(int i=0; i<N; ++i) 7d2fe88cb2 2012-09-08 kinaba: for(int j=0; j<N; ++j) 7d2fe88cb2 2012-09-08 kinaba: for(int k=0; k<N; ++k) 7d2fe88cb2 2012-09-08 kinaba: c[i][j] += a[i][k]*b[k][j]; 7d2fe88cb2 2012-09-08 kinaba: return c; 7d2fe88cb2 2012-09-08 kinaba: } 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: template<typename T> 7d2fe88cb2 2012-09-08 kinaba: vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v) 23dfcca431 2011-02-23 kinaba: { 7d2fe88cb2 2012-09-08 kinaba: for(; e; e>>=1, a=MATMUL(a,a)) 7d2fe88cb2 2012-09-08 kinaba: if(e&1) 7d2fe88cb2 2012-09-08 kinaba: v = MATMUL(a, v); 7d2fe88cb2 2012-09-08 kinaba: return v; 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 7d2fe88cb2 2012-09-08 kinaba: template<typename T> 7d2fe88cb2 2012-09-08 kinaba: vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) 23dfcca431 2011-02-23 kinaba: { 7d2fe88cb2 2012-09-08 kinaba: int N = a.size(); 7d2fe88cb2 2012-09-08 kinaba: vector< vector<T> > c(N, vector<T>(N)); 7d2fe88cb2 2012-09-08 kinaba: for(int i=0; i<N; ++i) c[i][i] = 1; 7d2fe88cb2 2012-09-08 kinaba: for(; e; e>>=1) { 7d2fe88cb2 2012-09-08 kinaba: if(e&1) 7d2fe88cb2 2012-09-08 kinaba: c = MATMUL(c, a); 7d2fe88cb2 2012-09-08 kinaba: a = MATMUL(a, a); 7d2fe88cb2 2012-09-08 kinaba: } 7d2fe88cb2 2012-09-08 kinaba: return c; 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 7d2fe88cb2 2012-09-08 kinaba: /**************************************************************************** 7d2fe88cb2 2012-09-08 kinaba: NOTES ON THE USAGE 7d2fe88cb2 2012-09-08 kinaba: **************************************************************************** 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: A[to][from] = #transition 7d2fe88cb2 2012-09-08 kinaba: -------------------------------------------- 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: frm 7d2fe88cb2 2012-09-08 kinaba: (. . .) (q0) 7d2fe88cb2 2012-09-08 kinaba: to (. . .) (q1) 7d2fe88cb2 2012-09-08 kinaba: (. . .) (q2) 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: qi 7d2fe88cb2 2012-09-08 kinaba: -------------------------------------------- 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: frm 7d2fe88cb2 2012-09-08 kinaba: (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: to (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: (0 1 0 1) (0) 7d2fe88cb2 2012-09-08 kinaba: ^ 7d2fe88cb2 2012-09-08 kinaba: i 7d2fe88cb2 2012-09-08 kinaba: Then, 7d2fe88cb2 2012-09-08 kinaba: q[i]@0 = (A^1 v)[$-1] 7d2fe88cb2 2012-09-08 kinaba: q[i]@0 + q[i]@1 = (A^2 v)[$-1] 7d2fe88cb2 2012-09-08 kinaba: q[i]@0 + ... + q[i]@k = (A^(k+1) v)[$-1] 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: q_all 7d2fe88cb2 2012-09-08 kinaba: -------------------------------------------- 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: frm 7d2fe88cb2 2012-09-08 kinaba: (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: to (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: (. . . 0) (.) 7d2fe88cb2 2012-09-08 kinaba: (1 1 1 1) (0) 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: Then, 7d2fe88cb2 2012-09-08 kinaba: q @0 = (A^1 v)[$-1] 7d2fe88cb2 2012-09-08 kinaba: q @0 + ... + q @k = (A^(k+1) v)[$-1] 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: Application: x^0 + x^1 + ... + x^e-1 7d2fe88cb2 2012-09-08 kinaba: -------------------------------------------- 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: (x 0)^e (1) = (x^e ) 7d2fe88cb2 2012-09-08 kinaba: (1 1) (0) (x^0 + x^1 + ... + x^e-1) 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: 23dfcca431 2011-02-23 kinaba: 7d2fe88cb2 2012-09-08 kinaba: Application: e x^0 + (e-1) x^1 + ... + 1 x^e-1 7d2fe88cb2 2012-09-08 kinaba: -------------------------------------------- 23dfcca431 2011-02-23 kinaba: 7d2fe88cb2 2012-09-08 kinaba: (x 0 0)^e (x) = (x^e+1 ) 7d2fe88cb2 2012-09-08 kinaba: (1 1 0) (1) (x^0 + x^1 + ... + x^e ) 7d2fe88cb2 2012-09-08 kinaba: (0 1 1) (0) ( of = e x^0 + (e-1) x^1 + ... + 1 x^e-1) 7d2fe88cb2 2012-09-08 kinaba: */