pku3318 Matrix Multiplication

有三个矩阵A，B，C，问A*B是否C，(n^3)的算法会超时。

构造一个n*1的矩阵，由

A*B=C

A*B*X=C*X

A*(B*X)=C*X

那么在(n^2)的时间内就能判定一次。

View Code

 1 program pku3318(input,output);
 2 var
 3    x,y,z          : array[0..501,0..501] of int64;
 4    left,right,answer1 : array[0..501] of int64;
 5    n              : longint;
 6    rand              : array[0..501] of longint;
 7 procedure init;
 8 var
 9    i,j : longint;
10 begin
11    readln(n);
12    for i:=1 to n do
13    begin
14       for j:=1 to n do
15      read(x[i,j]);
16       readln;
17    end;
18    for i:=1 to n do
19    begin
20       for j:=1 to n do
21      read(y[i,j]);
22       readln;
23    end;
24    for i:=1 to n do
25    begin
26       for j:=1 to n do
27      read(z[i,j]);
28       readln;
29    end;
30 end; { init }
31 function check():boolean;
32 var
33    i : longint;
34 begin
35    for i:=1 to n do
36       if answer1[i]<>right[i] then
37      exit(false);
38    exit(true);
39 end; { check }
40 procedure main;
41 var
42    i,j     : longint;
43 begin
44    randomize;
45    for i:=1 to n do
46       rand[i]:=trunc(random(20000));
47    fillchar(left,sizeof(left),0);
48    for i:=1 to n do
49       for j:=1 to n do
50      inc(left[i],y[i,j]*rand[j]);
51    fillchar(answer1,sizeof(answer1),0);
52    for i:=1 to n do
53       for j:=1 to n do
54      inc(answer1[i],left[j]*x[i,j]);
55    fillchar(right,sizeof(right),0);
56    for i:=1 to n do
57       for j:=1 to n do
58      inc(right[i],rand[j]*z[i,j]);
59    if not check() then
60    begin
61       writeln('NO');
62       exit;
63    end;
64    writeln('YES');
65 end; { main }
66 begin
67    while not eof do
68    begin
69       init;
70       main;
71    end;
72 end.