I - Matrix God Gym - 101341I

这道题很直白，给出矩阵A,B,C；要你计算A*B是否等于C；
普通的$O(n^3)$方法一定超时，我一直在尝试用Strassen递归的方法，发现随机化算法会简单很多，随机构造两个矩阵r1和r2，一个是1*n维，一个是n*1维，将r1*a*b*r2计算出来，就是一个整数，然后在计算r1*c*r2，结果也是一个整数。比对两个整数是否相等，这是答案的必要不充分条件，所以我们多尝试几组这样的r1,r2就可以不断的逼近真实。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=3000+5;
const int mod = 1e9+7;
LL a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
LL res1[maxn],res2[maxn],r1[maxn],r2[maxn],resL,resR;

int main()
{
    srand(unsigned(time(NULL)));
    //freopen("input.in","r",stdin);
    int n;
    while(scanf("%d",&n)==1) {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%lld",&a[i][j]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%lld",&b[i][j]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%lld",&c[i][j]);

        bool door=true;
        for(int z =0;z<5;z++)
        {
            memset(res1,0,sizeof(res1));
            memset(res2,0,sizeof(res2));
            for(int i=0;i<n;i++)
            {
                r1[i] = rand();
                r2[i] = rand();
            }
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                    res1[i]+=(r1[j]*a[j][i])%mod;
                    res2[i]+=(b[i][j]*r2[j])%mod;
                    res1[i]%=mod;
                    res2[i]%=mod;
                }

            resL=resR=0;
            for(int i=0;i<n;i++)
                resL=(resL+(res1[i]*res2[i])%mod)%mod;

            memset(res1,0,sizeof(res1));
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    res1[i]=(res1[i]+(r1[j]*c[j][i])%mod)%mod;


            for(int i=0;i<n;i++)
                resR=(resR+(res1[i]*r2[i])%mod)%mod;
            if(resL!=resR){
                door=false;
                break;
            }
        }
        if(door)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}