TIOJ-2044

發表於 更新於 Disqus：

給一個$n\times m$的矩陣。

問該矩陣是否滿足每一條由左上到右下的對角線的數字都一樣。
記憶體上限為1M

$1\le N\times M\le 10^6$

乍看之下非常簡單的一題。
然而1M的記憶體上限甚至連開$10^6$的int陣列都會TLE。

那該怎麼辦呢?

實際上你會發現，我們只是要比對這一列的第二項到最後一項是不是跟上一列的第一項到倒數第二項一樣。
既然要比對，又要省空間–rolling hash!
就能做到時間複雜度$\mathcal{O}(NM)$，空間複雜度$\mathcal{O}(1)$。

因為很怕被卡常，所以寫了輸入優化，但我猜沒有優化單用printf scanf應該是可以的(?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>

int read() {
	char c = getchar();
	while(c > '9' || c < '0')
		c = getchar();
	int res = 0;
	while(c <= '9' && c >= '0') {
		res = res * 10 + (c ^ 48);
		c = getchar();
	}
	return res;
}

constexpr int C = 1e9 + 151, MOD = 1e9 + 7;

signed main() {
	int t = read();
	while(t--) {
		int n = read(), m = read();
		bool ok = 1;
		long long prv;
		for(int i = 0; i < n; i++) {
			long long cur = 0, xcur = 0;
			for(int j = 0, w; j < m; j++) {
				w = read();
				if(j)
				 cur = (cur * C + w) % MOD;
				if(j < m - 1)
					xcur = (xcur * C + w) % MOD;
			}
			if(i)
				ok &= prv == cur;
			prv = xcur;
		}
		puts(ok ? "Yes" : "No");
	}
}