「BZOJ2396」神奇的矩阵
Description
给出三个行数和列数均为N的矩阵A、B、C，判断A*B=C是否成立。
Input
题目可能包含若干组数据。
对于每组数据，第一行一个数N，接下来给出三个N*N的矩阵，依次为A、B、C三个矩阵。
Output
对于每组数据，若A*B=C成立，则输出Yes，否则No。每个答案占一行。
Sample Input
1
2
2
100
2
2
100
Sample Output
No
HINT
对于90%的数据，N不超过100；
对于100%的数据，N不超过1000，矩阵中的数字大于等于0小于1000，数据组数不超过5组。
Source
随机生成一个N乘1的矩阵R
然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)
与后者一样都可以在O(N2)的时间里算出来
如果算出来的结果相等
A*B和C几乎也相等。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n; int a[1001][1001],b[1001][1001],c[1001][1001]; int rnd[1001],ans1[1001],ans2[1001]; void mmul(int a[1001],int b[1001][1001],int s[1001]) { int tmp[1001]; for(int j=1;j<=n;j++) { tmp[j]=0; for(int k=1;k<=n;k++) tmp[j]+=a[k]*b[k][j]; } for(int i=1;i<=n;i++)s[i]=tmp[i]; } bool jud() { for(int i=1;i<=n;i++) if(ans1[i]!=ans2[i])return 0; return 1; } int main() { for(int i=1;i<=1000;i++)rnd[i]=rand(); while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&b[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&c[i][j]); mmul(rnd,a,ans1); mmul(ans1,b,ans1); mmul(rnd,c,ans2); if(jud())printf("Yes\n"); else printf("No\n"); } return 0; } |
计数器 9787676
OI 课件=>
OI 课件=>
请问为什么mul函数里面要用tmp中转一下啊，不用的话就错？