2013
11-12

# Matrix Multiplication

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

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 description 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 "YES" if the equation holds true, otherwise "NO".

2
1 0
2 3
5 1
0 8
5 1
10 26


YES

Multiple inputs will be tested. So O(n3) algorithm will get TLE.

//* @author: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
int[][] p1=new int[a][a];
int[][] p2=new int[a][a];
int[][] p3=new int[a][a];
for(int i=0;i< a;i++)
{
for(int j=0;j< a;j++)
p1[i][j]=Integer.parseInt(ss[j]);
}
for(int i=0;i< a;i++)
{
for(int j=0;j< a;j++)
p2[i][j]=Integer.parseInt(ss[j]);
}
for(int i=0;i< a;i++)
{
for(int j=0;j< a;j++)
p3[i][j]=Integer.parseInt(ss[j]);
}
int i;
if(a< 50) i=Math.min(2000, a*a);
else if(a< 100) i=5000;
else i=50000;
while((i--)>0)
{
int x=(int)(Math.random()*a);
int y=(int)(Math.random()*a);
int ans=0;
for(int j=0;j< a;j++)
ans+=p1[x][j]*p2[j][y];
if(ans!=p3[x][y]) break;
}
if(i==-1) System.out.println("YES");
else System.out.println("NO");
}
}

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

3. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

4. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）