思路：

递推 + 快速幂优化。

实现：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 typedef vector
       
        
          > matrix; 6  7 matrix multiply(matrix & a, matrix & b, int MOD) 8 { 9     matrix c(a.size(), vector
         
          (b[0].size()));10     for (int i = 0; i < a.size(); i++)11     {12         for (int k = 0; k < a[0].size(); k++)13         {14             for (int j = 0; j < b[0].size(); j++)15             {16                 c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;17             }18         }19     }20     return c;21 }22 23 matrix pow(matrix & a, int n, int m)24 {25     matrix res(a.size(), vector
          
           (a[0].size()));26 for (int i = 0; i < a.size(); i++)27 {28 res[i][i] = 1;29 }30 while (n > 0)31 {32 if (n & 1)33 res = multiply(res, a, m);34 a = multiply(a, a, m);35 n >>= 1;36 }37 return res;38 }39 40 int main()41 {42 int n, k, m;43 cin >> n >> k >> m;44 matrix a(n * 2, vector
           
            (n, 0)), b(n * 2, vector
            
             (n * 2, 0));45 for (int i = 0; i < n; i++)46 {47 for (int j = 0; j < n; j++)48 {49 cin >> b[i][j];50 }51 }52 for (int i = 0; i < n; i++)53 {54 a[i][i] = b[n + i][i] = b[n + i][n + i] = 1;55 }56 matrix b_k = pow(b, k + 1, m);57 matrix ans = multiply(b_k, a, m);58 for (int i = 0; i < n; i++)59 {60 for (int j = 0; j < n; j++)61 {62 int tmp = ans[n + i][j];63 if (i == j) tmp = (tmp - 1 + m) % m;64 cout << tmp << " ";65 }66 cout << endl;67 }68 return 0;69 }