POJ 3233 Matrix Power Series 矩阵乘法 - c++编程基础

就算是水题了...因为K比较大所以在加起来的时候用分治

矩阵快速幂也是用分治的思想

所以就是分治+分治的一个水题了...

做这个题主要是为了自己写个模板防止以后出类似的题傻逼调试不出来...

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS 1e-8
#define MAXN 500050
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
//#define MOD 99991
//#define MOD 99990001
//#define MOD 1000000007
#define max(a,b) ((a)>(b) (a):(b))
#define min(a,b) ((a)<(b) (a):(b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define mabs(a) ((a<0) (-a):a)
#define L(t) (t << 1) //Left son t*2
#define R(t) (t << 1 | 1) //Right son t*2+1
#define Mid(a,b) ((a+b)>>1) //Get Mid
#define lowbit(a) (a&-a) //Get Lowbit
int gcd(int a,int b){return b gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct matrix
{
int ma[35][35];
}first,result;
int n,k,m;
/*矩阵乘法*/
matrix operator * (matrix a,matrix b)
{
matrix temp;
memset(temp.ma,0,sizeof(temp.ma));
for(int i = 0; i < n ; i++)
for(int j = 0; j < n ; j++)
for(int k = 0 ; k < n ; k++)
temp.ma[i][j] = (temp.ma[i][j] + (a.ma[i][k] * b.ma[k][j]) % m) % m ;
return temp;
}
/*矩阵加法*/
matrix operator +(matrix a,matrix b)
{
for(int i = 0; i < n ; i++)
for(int j = 0; j < n ; j++)
a.ma[i][j] = (a.ma[i][j] + b.ma[i][j]) % m;
return a;
}
/*矩阵快速幂*/
matrix m_pow(matrix a, int n)
{
if(n == 1)
return a;
matrix temp = m_pow(a,n/2);
if(n & 1)
return temp * temp * a;
else
return temp * temp ;

}
/*分治解决!*/
matrix solve(matrix a,int now)
{
if(now == 1)
return a ;
int mid = now>>1;
matrix temp = solve(a,mid);
if(now & 1)
return temp + (m_pow(a,mid) * (temp + m_pow(a,mid+1))) ;
else
return temp + (m_pow(a,mid) * temp);
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt,"w",stdout);
cin>>n>>k>>m;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
scanf("%d",&first.ma[i][j]);
result = solve(first,k);
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
cout< cout< }
return 0;
}