题目非常有简单：
Description
Given a n × n matrix A and a positive integer k, find the sum
S = A + A2 + A3 + … +
Ak.
Output
S mod m
范围：n (n ≤ 30), k (k ≤ 109) and
m (m < 104).
显然，暴力是不能解决这个问题，这题目非常有意思，并且不会非常难想。
我採取的是递归二分求解：
当k 为偶数： 能够化为 (A+ A ^2 +...+A^(k/2) )+A^(k/2)*(A+ A ^2 +...+A^(k/2)) ;
比方 k=6, 就能够化为 (A+A^2+A^3)+(A^3)*(A+A^2+A^3)，问题就转化为A+A^2+A^3，之后对A^3进行高速幂乘。
当k为奇数: 能够化为 k-1情况解+ (A^k)
这题目非常有意思，就是再求和用了一个二分，在求幂也用了二分。
我写得比較慢，重载了非常多符号，强迫症，为了好看。。。。
| 13577997 | dengyaolong | 3233 | Accepted | 896K | 1672MS | C++ | 2867B | 2014-10-29 17:10:35 |
/***********************************************************
> OS : Linux 3.13.0-24-generic (Mint-17)
> Author : yaolong
> Mail : dengyaolong@yeah.net
> Time : 2014年10月29日 星期三 16时05分45秒
**********************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
struct Matrix
{ int a[31][31];
int size;
int mod;
Matrix ( int s, int m ) : size ( s ), mod ( m )
{
for ( int i = 1; i <= s; i++ )
{
a[i][i] = 1;//单位矩阵
}
}
Matrix operator * ( const Matrix &rhs ) const //简单的乘法
{
Matrix res ( size, mod );
for ( int i = 1; i <= size; i++ )
{
for ( int j = 1; j <= size; j++ )
{
res.a[i][j] = 0;
for ( int k = 1; k <= size; k++ )
{
res.a[i][j] = ( res.a[i][j] + ( a[i][k] * rhs.a[k][j] ) ) % mod;
}
}
}
return res;
}
Matrix operator + ( const Matrix &rhs ) const//更简单得加法
{
Matrix res ( size, mod );
for ( int i = 1; i <= size; i++ )
{
for ( int j = 1; j <= size; j++ )
{
res.a[i][j] = ( a[i][j] + rhs.a[i][j] ) % mod;
}
}
return res;
}
Matrix operator ^ ( int p ) //高速幂
{
Matrix r ( size, mod );
Matrix base ( *this );
while ( p )
{
if ( p & 1 )
{
r = r * base;
}
base = base * base;
p >>= 1;
}
return r;
}
void print() //输出
{
for ( int i = 1; i <= size; i++ )
{
for ( int j = 1; j <= size; j++ )
{
if ( j > 1 )
{
cout << " ";
}
cout << a[i][j] ;
}
cout << endl;
}
}
void input() //输入
{
for ( int i = 1; i <= size; i++ )
{
for ( int j = 1; j <= size; j++ )
{
cin >> a[i][j];
a[i][j] = a[i][j] % mod;
}
}
}
};
Matrix PowerPlus ( Matrix m, int k )
{
if ( k == 1 ) //仅仅有一时候就直接返回
{
return m;
}
if ( k & 1 )
{
Matrix t = PowerPlus ( m, k >> 1 );
return ( m ^ k ) + t + ( m ^ ( k >> 1 ) ) * t ;
}
else
{
Matrix t = PowerPlus ( m, k >> 1 );
return t + ( m ^ ( k >> 1 ) ) * t;
}
}
int main()
{
int size, k, mod;
cin >> size >> k >> mod ;
Matrix mtr ( size, mod );
mtr.input();
( PowerPlus ( mtr, k ) ).print();
return 0;
}