k <= 10⁹ 暴力肯定超时

根据矩阵性质，可以发现

S(4) = A¹ + A² + A² * (A¹ + A²)

S(5) = A¹ + A² + A² * (A¹ + A²) + A⁵

所以可以递归二分求解，分别判断 A^k，k 为奇数和偶数的情况

 

——代码

1 #include 
      
        2 #include 
       
         3  4 struct Matrix 5 { 6     int a[30][30]; 7     Matrix() 8     { 9         memset(a, 0, sizeof(a));10     }11 };12 13 int n, k, p;14 Matrix I, P;15 16 inline Matrix operator * (const Matrix x, const Matrix y)17 {18     Matrix ans;19     int i, j, k;20     for(i = 0; i < n; i++)21         for(j = 0; j < n; j++)22             for(k = 0; k < n; k++)23                 ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % p;24     return ans;25 }26 27 inline Matrix operator + (const Matrix x, const Matrix y)28 {29     Matrix ans;30     int i, j;31     for(i = 0; i < n; i++)32         for(j = 0; j < n; j++)33             ans.a[i][j] = (ans.a[i][j] + x.a[i][j] + y.a[i][j]) % p;34     return ans;35 }36 37 inline Matrix operator ^ (Matrix x, int y)38 {39     Matrix ans = I;40     while(y)41     {42         if(y & 1) ans = ans * x;43         x = x * x;44         y >>= 1;45     }46     return ans;47 }48 49 inline Matrix work(Matrix x, int y)50 {51     if(!y) return P;52     Matrix ans = work(x, y >> 1);53     ans = ans + (x ^ (y >> 1)) * ans;54     if(y & 1) ans = ans + (x ^ y);55     return ans; 56 }57 58 int main()59 {60     int i, j;61     Matrix ans;62     for(i = 0; i < 30; i++) I.a[i][i] = 1;63     while(~scanf("%d %d %d", &n, &k, &p))64     {65         for(i = 0; i < n; i++)66             for(j = 0; j < n; j++)67                 scanf("%d", &ans.a[i][j]);68         ans = work(ans, k);69         for(i = 0; i < n; i++)70         {71                 for(j = 0; j < n; j++) printf("%d ", ans.a[i][j]);72                 puts("");73            }74     }75     return 0;76 }