2012-10-09 20:15:23Morris
[ZJ] a473. 外援計畫
內容
：
| 外援計畫 |
Background
小光上了大學之後，隔了一年考了轉學考，想說到新的學校會不會有比 ACM-ICPC 的隊友存在，但沒想到另一面臨的問題使得小光更加地沮喪。而這個問題，小光無法好好的敘述清楚，原因都是他的語文能力太差，講起話來大多語無倫次，連想為大家出一個好題目都辦不到。
上線性代數小考的時候，沒想到同班同學火速交卷，小光萬萬沒想到同學們算矩陣特別得快速、精準度也十分地好，相較之下，小光即使算出來了，錯誤率極高，總是希望有人可以幫他驗算，但是小光的朋友很少，希望你幫幫他。
The Problem
給定三個 N 階矩陣 A B C，小光利用公式(AB = C)已經算出 C，請驗證C的正確與否。
輸入說明
：
輸入的每一行包含多筆測試。一個測試資料遞一行包含一個整數 N，0 < N ≦ 500。
接下來有 N 行，每行上有 N 個整數 Aij 。
接下來有 N 行，每行上有 N 個整數 Bij 。
接下來有 N 行，每行上有 N 個整數 Cij 。
任何數字一定可以在 long long(64bits) 儲存。
輸出說明
：
輸出 "YES" 或者是 "NO"。
範例輸入 ：
2 1 2 3 4 5 7 6 8 17 23 39 53
範例輸出 ：
YES
提示
：
出處
：
(管理：morris1028)
擷取至 Matrix67 文章點此
脑海中出现的另一个牛B算法题则是POJ3318： 给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基 于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算 出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。
/**********************************************************************************/
/* Problem: a473 "外援計畫" from */
/* Language: C (1112 Bytes) */
/* Result: AC(312ms, 6.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-10-08 14:39:11 */
/**********************************************************************************/
#include <stdio.h>
#define FOR(i,n) for(i=0;i<n;i++)
#define LL long long
#define N 505
LL A[N][N], B[N][N], C[N][N], R[N], D[N], E[N];
int n, i, j;
int solve() {
FOR(i,n)
R[i] = i+1, D[i] = E[i] = 0;
FOR(i,n)FOR(j,n)
E[i] += C[i][j]*R[j];
FOR(i,n)FOR(j,n)
D[i] += B[i][j]*R[j];
FOR(i,n) R[i] = 0;
FOR(i,n)FOR(j,n)
R[i] += A[i][j]*D[j];
FOR(i,n)
if(R[i] != E[i])
return 0;
return 1;
}
LL ReadInt(LL *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
while(scanf("%d", &n) == 1) {
FOR(i,n)FOR(j,n)
ReadInt(&A[i][j]);
FOR(i,n)FOR(j,n)
ReadInt(&B[i][j]);
FOR(i,n)FOR(j,n)
ReadInt(&C[i][j]);
if(solve())
puts("YES");
else
puts("NO");
}
return 0;
}