A mul B Problem (KUPC 2012 Practice)

http://kupc2012pr.contest.atcoder.jp/tasks/kupc2012pr_4#

問題

略

解法

ヒントに書いてある通り。1000*1000だったので普通の行列乗算でも通ってしまった。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
int a[1010][1010];
int b[1010][1010];
int c[1010][1010];
int vect1[1010];
int vect2[1010];
int temp1[1010];
int temp2[1010][1010];

void PrintMat(int mat[1010][1010]) {
  REP(y, n) {
    REP(x, n) {
      printf("%d ", mat[y][x]);
    }
    puts("");
  }
  puts("");
}

void Mul(int mat1[1010][1010], int mat2[1010][1010]) {
  MEMSET(temp2, 0);
  REP(y, n) {
    REP(x, n) {
      REP(i, n) {
        temp2[y][x] += mat1[y][i] * mat2[i][x];
      }
    }
  }
  memcpy(mat1, temp2, sizeof(temp2));
}

void Mul(int mat[1010][1010], int v[1010]) {
  MEMSET(temp1, 0);
  REP(y, n) {
    REP(x, n) {
      temp1[y] += mat[y][x] * v[x];
    }
  }
  memcpy(v, temp1, sizeof(temp1));
}

void LoadMat(int mat[1010][1010]) {
  REP(y, n) {
    REP(x, n) {
      int v = scanf("%d", &mat[y][x]);
      assert(v == 1);
    }
  }
}

int main() {
  while (scanf("%d", &n) > 0) {
    LoadMat(a);
    LoadMat(b);
    LoadMat(c);
    bool ok = true;
    REP(iter, 100) {
      REP(i, n) { vect1[i] = vect2[i] = rand() % 2; }
      Mul(b, vect1);
      Mul(a, vect1);
      Mul(c, vect2);
      REP(i, n) {
        if (vect1[i] != vect2[i]) { ok = false; break; }
      }
    }
    puts(ok ? "YES" : "NO");
  }
}