[TIOJ] 1936. 雖然我是工具，但是我樂在其中

題目連結:http://tioj.infor.org/problems/1936

---

這題其實我覺得滿難的，一開始我一直以為他是簡單的矩陣乘法題，結果發現時間好像會超時，然後看了2015校隊培訓講義，發現原來是某種隨機演算法，想說那就直接隨機戳驗驗看吧，結過送了後一直TLE才估了一下複雜度發現也還是慘慘的，然後就莫名被雷到了，發現原來是隨機生成一個$n \times 1$的矩陣然後跟其他人乘，然後因為矩陣乘法有交換律(若$A \times B = C$，則$A \times B \times L = C \times L \rightarrow A \times (B \times L) = C \times L $)，所以若發現$ABL \neq CL$，那AB不等於C，但若$ABL=CL$也不代表$AB=C$所以多生個幾個L算一下吧

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef long long lld;

lld mA[1024 + 10][1024 + 10], mB[1024 + 10][1024 + 10], mC[1024 + 10][1024 + 10], l[1024 + 10];
int n;

inline void times(lld[][1024+10],lld[],lld[]);
inline bool same(lld[],lld[]);

int main(){
	srand(time(NULL));
	int T;
	gn(T);
	while(T--){
		gn(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				scanf("%lld",&mA[i][j]);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				scanf("%lld",&mB[i][j]);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				scanf("%lld",&mC[i][j]);
		bool tf=true;
		for(int i=0;i<5;i++){
			for(int i=0;i<n;i++)
				l[i]=rand()%10000;
			lld arrB[1024 + 10];
			times(mB,l,arrB);
			lld arrA[1024 + 10];
			times(mA,arrB,arrA);
			lld arrC[1024 + 10];
			times(mC,l,arrC);
			if(!same(arrA,arrC)){
				puts("QAQ!");
				tf=false;
				break;
			}
		}
		if(tf)
			puts("Loli is god.");
	}
}

inline void times(lld a[][1024+10], lld b[], lld c[]){
	for(int i=0;i<n;i++){
		c[i]=0;
		for(int j=0;j<n;j++){
			c[i] += a[i][j]*b[j];
		}
	}
}

inline bool same(lld a[],lld b[]){
	for(int i=0;i<n;i++)
		if(a[i]!=b[i])
			return false;
	return true;
}