| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么我的代码会2000+MS,求教!快吐血了。。#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int m , n;
class Matrix
{
public:
int a[35][35];
int n;
Matrix(int n , int f = 0)
{
this -> n = n;
memset(a,0,sizeof(a));
if(f == 1)
for(int i = 0 ; i < n ; i++)
a[i][i] = 1;
}
void build()
{
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
scanf("%d", &a[i][j]);
}
Matrix operator * (Matrix b)
{
Matrix c(n);
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
for(int k = 0 ; k < n ; k++)
{
c.a[i][j] += a[i][k] * b.a[k][j] % m;
c.a[i][j] %= m;
}
return c;
}
Matrix operator + (Matrix b)
{
Matrix c(n);
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j ++)
{
c.a[i][j] += a[i][j] + b.a[i][j];
c.a[i][j] %= m;
}
return c;
}
void show()
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
printf("%d",a[i][j]);
if(j == n-1)
printf("\n");
else
printf(" ");
}
}
}
};
Matrix pow(Matrix a, int k)
{
Matrix ans(n,1);
while(k > 0)
{
if(k&1)
ans = ans * a;
k >>= 1;
a = a * a;
}
return ans;
}
Matrix sum( Matrix p , int k)
{
Matrix E(n,1);
if(k == 1)
return p;
if(k&1)
return pow(p,k) + sum(p , k>>1) * ( pow(p , k>>1) + E);
return sum(p , k>>1) * ( pow(p , k>>1) + E );
}
int main()
{
int k;
scanf("%d%d%d",&n,&k,&m);
Matrix p(n);
p.build();
Matrix a = sum(p, k);
a.show();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator