[codeforces gym Matrix God]随机矩阵乘法
题目链接：http://codeforces.com/gym/101341/problem/I
随机真是一个神奇的方法。原本矩阵乘法是n^3的复杂度，但是这个题是让判断两个矩阵是否相等，只需要在两个矩阵分别左乘一个1*n的矩阵，右乘一个n*1的矩阵，这样两个矩阵就被压缩成了一个数，类似于特征值。只需判断这两个数是否相等即可。
那么如何生成这两个矩阵呢？随机数。如果怕不保险可以多随机几次，有一次不相等就算不相等，每次都相等就算相等。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int md=1000000007;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
int r1[maxn],r2[maxn];
int res1[maxn],res2[maxn],resL,resR;
int main()
{
srand(unsigned(time(NULL)));
int n;
scanf("%d",&n);
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]);
bool flag=true;
for (int z=1;z<=5;z++)
{
for (int i=1;i<=n;i++) r1[i]=rand(); //1*n
for (int i=1;i<=n;i++) r2[i]=rand(); //n*1
for (int i=1;i<=n;i++) res1[i]=res2[i]=0;
resL=resR=0;
for (int i=1;i<=n;i++) //r1*a and b*r2
{
for (int j=1;j<=n;j++)
{
res1[i]=(res1[i]+1ll*r1[j]*a[j][i]%md)%md;
res2[i]=(res2[i]+1ll*r2[j]*b[i][j]%md)%md;
}
}
for (int i=1;i<=n;i++) resL=(resL+1ll*res1[i]*res2[i]%md)%md;
for (int i=1;i<=n;i++) res1[i]=res2[i]=0;
for (int i=1;i<=n;i++) //r1*c
{
for (int j=1;j<=n;j++)
{
res1[i]=(res1[i]+1ll*r1[j]*c[j][i]%md)%md;
}
}
for (int i=1;i<=n;i++) resR=(resR+1ll*res1[i]*r2[i]%md)%md;
if (resL!=resR)
{
flag=false;
break;
}
}
if (flag) printf("YES\n");
else printf("NO\n");
return 0;
}
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。