矩阵快速幂模

2019-04-13 12:15发布

站内文章 / 模拟电子
12462 0 1064
print?
  1. #include    
  2. #include    
  3. #include    
  4. #include    
  5. using namespace std;  
  6. #define MAXN 12   
  7. #define M 9973   
  8. typedef struct  
  9. {  
  10.       int m[MAXN][MAXN];  
  11. }Matrix;  
  12.   
  13. Matrix a, per;  
  14. int n;  
  15.   
  16. void init()  
  17. {  
  18.      for(int i = 0; i < n; i ++)  
  19.               for(int  j = 0;j < n; j ++)  
  20.               {  
  21.                        scanf("%d", &a.m[i][j]);  
  22.                        a.m[i][j] = a.m[i][j] % M;  
  23.                        per.m[i][j] = (i==j);  
  24.               }  
  25. }  
  26.   
  27. Matrix multi(Matrix a, Matrix b)  
  28. {  
  29.      Matrix c;  
  30.      for(int i = 0; i < n; i ++)  
  31.      {  
  32.              for(int j = 0; j < n; j ++)  
  33.              {  
  34.                       c.m[i][j] = 0;  
  35.                       for(int k = 0; k < n; k ++)  
  36.                       {  
  37.                               c.m[i][j] = c.m[i][j] + a.m[i][k] * b.m[k][j] % M;  
  38.                       }  
  39.                       c.m[i][j] = c.m[i][j] % M;  
  40.              }  
  41.      }  
  42.      return c;  
  43. }  
  44.   
  45. int  power(int k)  
  46. {  
  47.       Matrix c, p, ans = per;  
  48.       p = a;  
  49.       while(k)  
  50.       {  
  51.               if(k & 1) ans = multi(ans, p);  
  52.               k = k / 2;  
  53.               p = multi(p, p);  
  54.       }  
  55.       int  sum = 0;  
  56.       for(int i = 0; i <  n; i ++)  
  57.       {  
  58.               sum = (sum + ans.m[i][i]) % M;  
  59.       }  
  60.       return sum % M;  
  61. }  
  62.   
  63. int  main()  
  64. {  
  65.      int t, k;  
  66.      scanf("%d", &t);  
  67.      for(int i = 0; i < t; i ++)  
  68.      {  
  69.              scanf("%d %d", &n, &k);  
  70.              init();  
  71.              int ans = power(k);  
  72.              printf("%d ", ans);  
  73.      }  
  74.      return 0;  
  75. }  

热门文章