QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238598#5440. P-P-PalindromeNetwork_ErrorWA 6ms18164kbC++141.6kb2023-11-04 17:06:112023-11-04 17:06:11

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 17:06:11]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:18164kb
  • [2023-11-04 17:06:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
int n, r, s[1000010], ans; 
unsigned int hsh[1000010], bpw[1000010]; const int base = 29, mod = 100000000000000049; map<unsigned int, int> p;
int tot, lst, tr[1000010][26], bor[1000010], len[1000010]; 
void init() {
	tot = 1; len[1] = -1; bor[0] = 1;
} 
unsigned int gethsh(int l, int r) {
	return (hsh[r] + mod - hsh[l - 1] * bpw[r - l + 1] % mod);
}
void extend(int c) {
	deb(c);
	s[++r] = c + 1;
	int u = lst;
	while (s[r] != s[r - len[u] - 1]) u = bor[u];
	if (!tr[u][c]) {
		int v = ++tot; len[v] = len[u] + 2; bor[v] = bor[u];
		while (s[r] != s[r - len[bor[v]] /*shaber mistake*/ - 1]) bor[v] = bor[bor[v]];
		bor[v] = tr[bor[v]][c]; tr[u][c] = v;
		// 求 v 的最小整周期
		int d = len[v];
		if (len[v] % (len[v] - len[bor[v]]) == 0) d = len[v] - len[bor[v]];
		ans += p[gethsh(r - d + 1, r)]; p[gethsh(r - d + 1, r)]++;
	} lst = tr[u][c];
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	bpw[0] = 1; for (int i = 1; i <= 1e6; i++) bpw[i] = bpw[i - 1] * base % mod;
	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		r = lst = 0; 
		string s; cin >> s;
		hsh[0] = 1;
		for (int i = 0; i < s.size(); i++) {
			hsh[i + 1] = (hsh[i] * base + s[i] - 'a' + 1) % mod; extend(s[i] - 'a');
		}
	} cout << ans * 2 + tot - 1 << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 18088kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 6ms
memory: 15816kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 3ms
memory: 17980kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 18164kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1272

result:

wrong answer 1st numbers differ - expected: '1282', found: '1272'