看心情填坑

http://poj.org/problem?id=3318

题意不能更简单粗暴

随便弄一个1*N的矩阵R，因为矩阵乘法满足结合律，所以A*(B*R)=(A*B)*R,B*R的复杂度是N^2，C*R的复杂度是N^2,A*(B*R)的复杂度也是n^2，最后验证O(n)所以随机一次需要的复杂度是O(n²),多随机几次就能过啦。

我才不会告诉你只要加读入优化暴力就能过以及正确性期望我不会证

#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
int a[501][501],b[501][501],c[501][501],r[501],p[501],P[501],s[501];
int n;
bool ans;
inline int read(){
    int p=1,x;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')p=-1;
    x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';
    x*=p;
    return x;
}
inline bool work(){
	for(int i=1;i<=n;i++)r[i]=i;
	for(int i=1;i<=n;i++){
		p[i]=0;
		for(int j=1;j<=n;j++)p[i]+=b[i][j]*r[j];
	}
	for(int i=1;i<=n;i++){
		P[i]=0;
		for(int j=1;j<=n;j++)P[i]+=a[i][j]*p[j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)P[i]-=c[i][j]*r[j];
		if(P[i]!=0)return true;
	}
	return false;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)a[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)b[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)c[i][j]=read();
	if(work())printf("NO");
	else printf("YES");
}

只验证一次都要跑110ms,63ms的都是怪物