[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...