题解：P10102 [GDKOI2023 提高组] 矩阵

· · 题解

新接触到随机化算法，记录一下。

思路

题意很简单，考察矩阵乘法，不会的戳这里。

但矩阵乘法的时间复杂度是 \mathcal{O(n^3)} 的，这里 n\le 3000，显然不可行，于是我们考虑随机化，通过降低相乘矩阵规模优化时间复杂度。

我们可以每次构造一个随机的大小为 1\times n 的矩阵 D，根据等式的性质可以将符合条件的判断转化为 A\times B\times D = C\times D，这样，我们每次乘法的复杂度就降低到了 \mathcal{O(n^2)}，每组数据进行三次乘法，最终复杂度为 \mathcal{O(T\sum n^2)}，可以通过此题。

这样做法出现差错的概率极低，如果不放心可以多操作几次，不会明显影响时间复杂度。

实现

代码最工整的一集。

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)

const int Ratio=0;
const int N=3e3+5;
const int mod=998244353;
int T,n;
int a[N][N],b[N][N],c[N][N],d[2][N],e[2][N],f[2][N],g[2][N];
namespace Wisadel
{
    short main()
    {
        scanf("%d",&T);srand(time(0));
        while(T--)
        {
            scanf("%d",&n);bool can=1;
            fo(i,1,n) fo(j,1,n) scanf("%d",&a[i][j]);
            fo(i,1,n) fo(j,1,n) scanf("%d",&b[i][j]);
            fo(i,1,n) fo(j,1,n) scanf("%d",&c[i][j]);
            fo(i,1,n) d[1][i]=rand(),e[1][i]=0,f[1][i]=0,g[1][i]=0;
            fo(j,1,n) fo(k,1,n) e[1][j]=(e[1][j]+1ll*d[1][k]*a[k][j]%mod)%mod;
            fo(j,1,n) fo(k,1,n) f[1][j]=(f[1][j]+1ll*e[1][k]*b[k][j]%mod)%mod;
            fo(j,1,n) fo(k,1,n) g[1][j]=(g[1][j]+1ll*d[1][k]*c[k][j]%mod)%mod;
            fo(i,1,n) if(f[1][i]!=g[1][i]){can=0;break;}
            printf(can?"Yes\n":"No\n");
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~

Welcome\;to\;my\;blogs