POJ 3233 Matrix Power Series

题目：给出一个 n×n 的矩阵 A 和一个整数k, 求 S = A + A² + A³ + … + A^k.

其中n (n ≤ 30), k (k ≤ 10⁹) , m (m < 10⁴).

分析：两次二分，A^i可以用矩阵快速幂，然后求和二分。比如，当k=6时，有：A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)

--------------------------------------

我用的递归求和，程序很杯具的跑了2s……等有空再改改吧，写的真的很糟糕，主要是想练习一下二分。

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 35;
  5 
  6 struct Mat
  7 {
  8     int array[MAXN][MAXN];
  9     friend Mat operator*( Mat &a, Mat &b );
 10     friend Mat operator+( Mat &a, Mat &b );
 11     friend Mat operator^( Mat a, int k);
 12 };
 13 
 14 int n, MOD;
 15 Mat data;
 16 Mat UNIT;
 17 
 18 Mat operator*( Mat &a, Mat &b )
 19 {
 20     Mat temp;
 21 
 22     memset( temp.array, 0, sizeof(temp.array) );
 23 
 24     for ( int i = 0; i < n; i++ )
 25        for ( int j = 0; j < n; j++ )
 26            for ( int k = 0; k < n; k++ )
 27               temp.array[i][j] = ( temp.array[i][j] + a.array[i][k] * b.array[k][j]%MOD )%MOD;
 28 
 29     return temp;
 30 }
 31 
 32 Mat operator+( Mat &a, Mat &b )
 33 {
 34     Mat temp;
 35 
 36     memset( temp.array, 0, sizeof(temp.array) );
 37 
 38     for ( int i = 0; i < n; i++ )
 39        for ( int j = 0; j < n; j++ )
 40             temp.array[i][j] = ( a.array[i][j] + b.array[i][j] ) % MOD;
 41 
 42     return temp;
 43 }
 44 
 45 Mat operator^( Mat a, int k )
 46 {
 47     Mat unit = UNIT;
 48 
 49     while ( k )
 50     {
 51         if ( k&1 ) unit = unit * a;
 52         a = a * a;
 53         k >>= 1;
 54     }
 55 
 56     return unit;
 57 }
 58 
 59 Mat Sum( int k )
 60 {
 61     Mat temp;
 62     if ( k == 1 ) return temp = data;
 63 
 64     memset( temp.array, 0, sizeof(temp.array) );
 65 
 66     int tp = k >> 1;
 67 
 68     Mat temp2 = Sum( tp );
 69     Mat temp3 = data ^ tp;
 70 
 71     Mat temp1 = temp2 * temp3;
 72     temp = temp2 + temp1;
 73 
 74     if ( k&1 )
 75     {
 76         Mat temp4 = data ^ k;
 77         temp = temp + temp4;
 78     }
 79 
 80     return temp;
 81 }
 82 
 83 int main()
 84 {
 85     int k;
 86     memset( UNIT.array, 0, sizeof(UNIT.array) );
 87     for ( int i = 0; i < MAXN; i++ )
 88         UNIT.array[i][i] = 1;
 89 
 90     while ( scanf("%d%d%d", &n, &k, &MOD) != EOF )
 91     {
 92         for ( int i = 0; i < n; i++ )
 93            for ( int j = 0; j < n; j++ )
 94             {
 95                 scanf( "%d", &data.array[i][j] );
 96                 data.array[i][j] %= MOD;
 97             }
 98 
 99         Mat ans = Sum(k);
100 
101         for ( int i = 0; i < n; i++ )
102         {
103             printf( "%d", ans.array[i][0] );
104             for ( int j = 1; j < n; j++ )
105                printf( " %d", ans.array[i][j] );
106             putchar('\n');
107         }
108 
109     }
110     return 0;
111 }