davidwang's Blog

我还是太弱了

如何判断两个n*n的矩阵A，B的， A*B是否等于C

我们随机一个1*n的向量 x A*B=C 等价于 x*A*B=x*C，矩阵乘法满足结合律，所以这个判断就是$$ O(n^2) $$的

然后这道题目就是枚举答案然后判断就可以了复杂度 $$ O(ans * n^2) $$ 我试了以下貌似这玩意非常难卡掉，因为我去掉判断也过掉了到套题目

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
struct Matrix{
	int x[71][71];
	int h,w;
	int operator==(const Matrix &A) const{
		if (h!=A.h || w!=A.w) return 0;
		for (int i=1;i<=h;i++)
			for (int j=1;j<=w;j++)
				if (x[i][j]!=A.x[i][j]) return 0;
		return 1;
	}
}A,B,C,Tar,now;
int mod;
Matrix operator*(const Matrix &A,const Matrix &B){
	Matrix C;
	C.h=A.h; C.w=B.w;
	for (int i=1;i<=C.h;i++)
		for (int j=1;j<=C.w;j++) C.x[i][j]=0;
	for (int i=1;i<=C.h;i++)
		for (int j=1;j<=C.w;j++)
			for (int k=1;k<=A.w;k++)
				C.x[i][j]=(C.x[i][j]+A.x[i][k]*B.x[k][j])%mod;
	return C;
}
inline Matrix power(Matrix A,LL b){
	
//	printf("check %lld\n",b);	
	
	Matrix C;
	C.h=C.w=A.h;
	for (int i=1;i<=A.h;i++)
		for (int j=1;j<=A.h;j++)
			C.x[i][j]=i==j;
	while (b){
		if (b&1) C=C*A;
		A=A*A;
		b>>=1;
	}
	return C;
}
int n;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	srand(2333);
	n=read(); mod=read();
	A.h=A.w=B.h=B.w=C.w=n;
	C.h=1;
	for (int i=1;i<=n;i++) C.x[1][i]=rand()%(mod-1)+1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			A.x[i][j]=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			B.x[i][j]=read();
	Tar=C*B;
	now=C*A;
	int ans=1;
	while (1){
		if (Tar==now){
			printf("%d\n",ans);
			return 0;
		}
		now=now*A;
		ans++;
	}
	return 0;
}