AK-dream

【题目描述】
给你一个只包含大写字母的矩阵,求有多少本质不同的子矩阵。

【输入格式】
第一行包含两个整数 $n$ , $m$ ,表示矩阵 $n$ 行 $m$ 列 。
接下来 $n$ 行描述这个矩阵。

【输出格式】
只含一个整数,为本质不同的子矩阵个数。

先枚举长度$l$,然后将每个串压位哈希(哈希提前处理好就行)
盗用一张图

然后从上到下,从左到右,生成一个这样的串:ac$bc

对于每个长度$l$生成的新串 将这个新串的本质不同的子串个数累加到答案上
可以感性理解一下 枚举$l$就相当是枚举子矩阵的长度

多简单鸭

离散化写起来极其恶臭 迫不得已用了map(因为懒)
大家不要学我 离散化大法好

p.s. 模数998244353被卡到只有20分。。。要不用1e9+7要不用ull吧

【代码】

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define mul 1000000007ull
#define N 1000005
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n, m;
ull hsh[205][205], p[205];
char s[205][205];
int now;
ull t[20005], len, ans;
int sa[N], sa2[N], rnk[N], sum[N], key[N], height[N];
map<ull, int> mp;

inline bool check(int *num, int x, int y, int l) {
return num[x] == num[y] && num[x+l] == num[y+l];
}

inline void suffix(int n, int m) {
int i, j, p; int *_rnk = rnk, *_sa2 = sa2;
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[_rnk[i]=t[i]]++;
for (i = 2; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[_rnk[i]]--] = i;
for (j = 1; j <= n; j <<= 1, m = p) {
for (p = 0, i = n - j + 1; i <= n; i++) _sa2[++p] = i;
for (i = 1; i <= n; i++) if (sa[i] > j) _sa2[++p] = sa[i] - j;
for (i = 1; i <= n; i++) key[i] = _rnk[_sa2[i]];
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[key[i]]++;
for (i = 2; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[key[i]]--] = _sa2[i];
for (swap(_rnk, _sa2), i = 2, p = 2, _rnk[sa[1]] = 1; i <= n; i++) {
_rnk[sa[i]] = check(_sa2, sa[i-1], sa[i], j) ? p-1 : p++;
}
}
p = 0;
for (i = 1; i <= n; i++) rnk[sa[i]] = i;
for (i = 1; i <= n; i++) {
if (p) p--; j = sa[rnk[i]-1];
while (t[i+p] == t[j+p]) p++;
height[rnk[i]] = p;
}
}


int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", s[i]+1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
hsh[i][j] = (hsh[i][j-1] * mul + s[i][j]-'A'+1);
}
}
p[0] = 1;
for (int i = 1; i <= 200; i++) {
p[i] = p[i-1] * mul;
}
for (int l = 1; l <= m; l++) {
len = 0; now = 0; mp.clear();
for (int j = 1; j <= m - l + 1; j++) {
for (int i = 1; i <= n; i++) {
ull x = hsh[i][j+l-1] - hsh[i][j-1] * p[l];
if (!mp[x]) mp[x] = ++now;
t[++len] = mp[x];
}
t[++len] = ++now;
}
now += 10;
suffix(len, now);
ans += n * (n+1) / 2 * (m - l + 1);
for (int i = 1; i <= len; i++) {
ans -= height[i];
}
}
printf("%lld\n", ans);
return 0;
}


 评论