Artifact 2c92483914a46a5636fc57fdf4c53f62bfa9fd8e:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 4d 61 74 72 69 78 20 4f 70 65 72 61 .// Matrix Opera
0050: 74 69 6f 6e 73 0a 2f 2f 0a 2f 2f 20 56 65 72 69 tions.//.// Veri
0060: 66 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 53 fied by.// - S
0070: 52 4d 33 34 32 20 44 69 76 31 20 4c 56 33 0a 2f RM342 Div1 LV3./
0080: 2f 20 20 20 2d 20 53 52 4d 33 34 31 20 44 69 76 / - SRM341 Div
0090: 31 20 4c 56 33 0a 2f 2f 20 20 20 2d 20 53 52 4d 1 LV3.// - SRM
00a0: 33 33 38 20 44 69 76 31 20 4c 56 32 0a 2f 2f 2d 338 Div1 LV2.//-
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 76 65 ------------..ve
00f0: 63 74 6f 72 3c 4c 4c 3e 20 76 4d 75 6c 28 20 63 ctor<LL> vMul( c
0100: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 onst vector< vec
0110: 74 6f 72 3c 4c 4c 3e 20 3e 26 20 41 2c 20 63 6f tor<LL> >& A, co
0120: 6e 73 74 20 76 65 63 74 6f 72 3c 4c 4c 3e 26 20 nst vector<LL>&
0130: 42 20 29 0a 7b 0a 09 63 6f 6e 73 74 20 69 6e 74 B ).{..const int
0140: 20 6e 20 3d 20 41 2e 73 69 7a 65 28 29 3b 0a 0a n = A.size();..
0150: 09 76 65 63 74 6f 72 3c 4c 4c 3e 20 43 28 6e 29 .vector<LL> C(n)
0160: 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ;..for(int i=0;
0170: 69 3c 6e 3b 20 2b 2b 69 29 0a 09 09 66 6f 72 28 i<n; ++i)...for(
0180: 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b int j=0; j<n; ++
0190: 6a 29 0a 09 09 09 43 5b 69 5d 20 2b 3d 20 41 5b j)....C[i] += A[
01a0: 69 5d 5b 6a 5d 20 2a 20 42 5b 6a 5d 3b 0a 09 72 i][j] * B[j];..r
01b0: 65 74 75 72 6e 20 43 3b 0a 7d 0a 0a 76 65 63 74 eturn C;.}..vect
01c0: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
01d0: 20 6d 4d 75 6c 28 20 63 6f 6e 73 74 20 76 65 63 mMul( const vec
01e0: 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 tor< vector<LL>
01f0: 3e 26 20 41 2c 20 63 6f 6e 73 74 20 76 65 63 74 >& A, const vect
0200: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
0210: 26 20 42 20 29 0a 7b 0a 09 63 6f 6e 73 74 20 69 & B ).{..const i
0220: 6e 74 20 6e 20 3d 20 41 2e 73 69 7a 65 28 29 3b nt n = A.size();
0230: 0a 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f ...vector< vecto
0240: 72 3c 4c 4c 3e 20 3e 20 43 28 6e 2c 20 76 65 63 r<LL> > C(n, vec
0250: 74 6f 72 3c 4c 4c 3e 28 6e 29 29 3b 0a 09 66 6f tor<LL>(n));..fo
0260: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 r(int i=0; i<n;
0270: 2b 2b 69 29 0a 09 09 66 6f 72 28 69 6e 74 20 6a ++i)...for(int j
0280: 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 20 7b 0a =0; j<n; ++j) {.
0290: 09 09 09 4c 4c 20 43 69 6a 20 3d 20 30 3b 0a 09 ...LL Cij = 0;..
02a0: 09 09 66 6f 72 28 69 6e 74 20 6b 3d 30 3b 20 6b ..for(int k=0; k
02b0: 3c 6e 3b 20 2b 2b 6b 29 0a 09 09 09 09 43 69 6a <n; ++k).....Cij
02c0: 20 2b 3d 20 41 5b 69 5d 5b 6b 5d 20 2a 20 42 5b += A[i][k] * B[
02d0: 6b 5d 5b 6a 5d 3b 0a 09 09 09 43 5b 69 5d 5b 6a k][j];....C[i][j
02e0: 5d 20 3d 20 43 69 6a 3b 0a 09 09 7d 0a 09 72 65 ] = Cij;...}..re
02f0: 74 75 72 6e 20 43 3b 0a 7d 0a 0a 76 65 63 74 6f turn C;.}..vecto
0300: 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 r< vector<LL> >
0310: 6d 50 6f 77 28 20 76 65 63 74 6f 72 3c 20 76 65 mPow( vector< ve
0320: 63 74 6f 72 3c 4c 4c 3e 20 3e 20 4d 2c 20 4c 4c ctor<LL> > M, LL
0330: 20 74 20 29 20 2f 2f 20 74 3e 30 0a 7b 0a 09 76 t ) // t>0.{..v
0340: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c ector< vector<LL
0350: 3e 20 3e 20 52 3b 0a 09 66 6f 72 28 3b 20 74 3b > > R;..for(; t;
0360: 20 74 3e 3e 3d 31 2c 20 4d 3d 6d 4d 75 6c 28 4d t>>=1, M=mMul(M
0370: 2c 4d 29 29 0a 09 09 69 66 28 20 74 26 31 20 29 ,M))...if( t&1 )
0380: 0a 09 09 09 52 20 3d 20 28 52 2e 65 6d 70 74 79 ....R = (R.empty
0390: 28 29 20 3f 20 4d 20 3a 20 6d 4d 75 6c 28 52 2c () ? M : mMul(R,
03a0: 4d 29 29 3b 0a 09 72 65 74 75 72 6e 20 52 3b 0a M));..return R;.
03b0: 7d 0a 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 6f }..vector< vecto
03c0: 72 3c 4c 4c 3e 20 3e 20 6d 41 64 64 28 20 63 6f r<LL> > mAdd( co
03d0: 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 74 nst vector< vect
03e0: 6f 72 3c 4c 4c 3e 20 3e 26 20 41 2c 20 63 6f 6e or<LL> >& A, con
03f0: 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f st vector< vecto
0400: 72 3c 4c 4c 3e 20 3e 26 20 42 20 29 0a 7b 0a 09 r<LL> >& B ).{..
0410: 63 6f 6e 73 74 20 69 6e 74 20 6e 20 3d 20 41 2e const int n = A.
0420: 73 69 7a 65 28 29 3b 0a 0a 09 76 65 63 74 6f 72 size();...vector
0430: 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 43 < vector<LL> > C
0440: 28 6e 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 6e (n, vector<LL>(n
0450: 29 29 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 ));..for(int i=0
0460: 3b 20 69 3c 6e 3b 20 2b 2b 69 29 0a 09 09 66 6f ; i<n; ++i)...fo
0470: 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 r(int j=0; j<n;
0480: 2b 2b 6a 29 0a 09 09 09 43 5b 69 5d 5b 6a 5d 20 ++j)....C[i][j]
0490: 3d 20 41 5b 69 5d 5b 6a 5d 20 2b 20 42 5b 69 5d = A[i][j] + B[i]
04a0: 5b 6a 5d 3b 0a 09 72 65 74 75 72 6e 20 43 3b 0a [j];..return C;.
04b0: 7d 0a }.