[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=;

const int md=;

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=;i<=n;i++)

        for (int j=;j<=n;j++)

            scanf("%d",&a[i][j]);

    for (int i=;i<=n;i++)

        for (int j=;j<=n;j++)

            scanf("%d",&b[i][j]);

    for (int i=;i<=n;i++)

        for (int j=;j<=n;j++)

            scanf("%d",&c[i][j]);

    bool flag=true;

    for (int z=;z<=;z++)

    {

        for (int i=;i<=n;i++) r1[i]=rand();  //1*n

        for (int i=;i<=n;i++) r2[i]=rand();  //n*1

        for (int i=;i<=n;i++) res1[i]=res2[i]=;

        resL=resR=;

        for (int i=;i<=n;i++) //r1*a and b*r2

        {

            for (int j=;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=;i<=n;i++) resL=(resL+1ll*res1[i]*res2[i]%md)%md;

        for (int i=;i<=n;i++) res1[i]=res2[i]=;

        for (int i=;i<=n;i++) //r1*c

        {

            for (int j=;j<=n;j++)

            {

                res1[i]=(res1[i]+1ll*r1[j]*c[j][i]%md)%md;

            }

        }

        for (int i=;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 ;

}