1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 // 矩阵的STL实现 7 typedef vector
         
           vec; 8 typedef vector
          
            mat; 9 typedef long long ll;10 const int MOD = 10000;11 // 矩阵乘法12 mat mul(mat &A,mat &B){13 mat C(A.size(),vec(B[0].size()));14 for(int i = 0 ; i < A.size() ; i++)15 for(int k = 0 ; k < B.size() ; k++)16 for(int j = 0 ; j < B[0].size() ; j++)17 C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;18 return C;19 }20 // 矩阵快速幂21 mat pow(mat A,ll n){22 mat B(A.size(),vec(A.size()));23 for(int i = 0 ; i < A.size() ; i++)24 B[i][i] = 1;25 while(n > 0){26 if(n & 1) B = mul(B,A);27 A = mul(A,A);28 n >>= 1;29 }30 return B;31 }