Matrix Multiplication
| Time Limit: 2000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?
Input
The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix's descri_ption is a block of n × n integers.
It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.
Output
Output "YES" if the equation holds true, otherwise "NO".
Sample Input
2 1 0 2 3 5 1 0 8 5 1 10 26
Sample Output
YES
Hint
其时这既不是博弈也不是概率就是矩阵相乘（但是使用了巧妙的的方法是时间效率达到了O(n^2),我一开始可没想到）
题意：
给三个矩阵A
B C ，判断一下A * B = C，是的话输出YES ，否则输出NO。
分析：
正常的矩阵相乘都是O（n^3）但是提示都说了O（N^3）会TLE。没办法，搜报告。。
这个方法的巧妙也是我没能想到的
他他他竟然 X * A * B = X * C;X 为行矩阵。。。太巧妙了。。（ORZ，现在才知道ORZ是啥意思啊，相知恨晚啊。。）
http://blog.csdn.net/tao_tao_bu_jue/article/details/2785760
Code
| Problem: R | User: sdau_09_zys | |
| Memory: 6116 KB | Time: 1219 MS | |
| Language: C++ | Result: Accepted | |
| Public: | ||
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll a[505][505];
ll b[505][505];
ll c[505][505];
ll e[505];
ll E[505];
ll x[505];
int n;
bool cmp()
{
int i,j;
ll tem[505];
memset(tem,0,sizeof tem);
memset(E,0,sizeof E);
memset(e,0,sizeof e);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
tem[i]+=a[j][i]*(j+1);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
e[i]+=b[j][i]*tem[j];
}for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
E[i]+=c[j][i]*(j+1);
}
for(i=0;i<n;i++)
{
if(e[i]!=E[i])return false;
}
return true;
}
int main()
{
int i,j