Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么我的代码会2000+MS,求教!快吐血了。。

Posted by sherry521007 at 2012-11-19 00:54:54 on Problem 3233
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator