QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398242#5440. P-P-PalindromenKessiWA 87ms118952kbC++142.8kb2024-04-25 09:28:162024-04-25 09:28:17

Judging History

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

  • [2024-04-25 09:28:17]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:118952kb
  • [2024-04-25 09:28:16]
  • 提交

answer

/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#define pr pair <int, int>
#define mr make_pair
#define LL long long
#define ls tree[p].L
#define rs tree[p].R
#define uLL unsigned long long
using namespace std;
const int MAXN = 1e6 + 5, Mod = 998244353;
struct node {
	int son[27], fail, len, id, ed;
}pam[MAXN];
int n, las = 1, tot = 1, mb1, mb2, c[MAXN];
vector <int> v[MAXN];
string s[MAXN];
LL P[MAXN];
vector <LL> Hash[MAXN];
map <LL, int> mp;
void read(int &x) {
	x = 0; bool f = 1; char C = getchar();
	for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
	for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
	x = (f ? x : -x);
}
int getfail(int x) {
	while(s[mb1][mb2] != s[mb1][mb2 - pam[x].len - 1]) x = pam[x].fail;
	return x;
}
void ins(int x) {
	int p = getfail(las), now = pam[p].son[x];
	if(!now) {
		now = ++ tot; pam[now].len = pam[p].len + 2;
		pam[now].fail = pam[getfail(pam[p].fail)].son[x]; pam[p].son[x] = now;
		pam[tot].id = mb1; pam[tot].ed = mb2;
	}
	las = now; c[las] ++;
}
void dfs(int x) {
	for(auto y : v[x]) {
		dfs(y);
		c[x] += c[y]; //printf("?%d %d %d?\n", x, y, pam[y].len);
		if(pam[y].id) pam[x].id = pam[y].id, pam[x].ed = pam[y].ed;
	}
}
uLL gethash(int id, int l, int r) {
	return ((Hash[id][r] - (l ? Hash[id][l - 1] * P[r - l + 1] : 0)) % Mod + Mod) % Mod;
}
int main() {
	read(n); pam[0].len = 0; pam[1].len = -1; pam[0].fail = pam[1].fail = 1; P[0] = 1;
	for(int i = 1; i <= 1000000; i ++) P[i] = P[i - 1] * 2007391 % Mod;
	for(int i = 1; i <= n; i ++) {
		cin >> s[i]; las = 1; mb1 = i; Hash[i].resize(s[i].length());
		for(int j = 0; j < s[i].length(); j ++) mb2 = j, ins(s[i][j] - 'a');
		for(int j = 0; j < s[i].length(); j ++) {
			Hash[i][j] = s[i][j];
			if(j) Hash[i][j] += Hash[i][j - 1] * 2007391, Hash[i][j] %= Mod;
		}
	}
	v[1].emplace_back(0);
	for(int i = 2; i <= tot; i ++) v[pam[i].fail].emplace_back(i);
	dfs(1);
	for(int i = 2; i <= tot; i ++) {
//		if(c[i] != n) continue;
//		printf("|%d %d|\n", i, pam[i].len);
		if(pam[i].len == 1) {
			mp[gethash(pam[i].id, pam[i].ed, pam[i].ed)] ++; continue;
		}
		int len1 = pam[i].len, len2 = pam[pam[i].fail].len;
		if(len1 % (len1 - len2) == 0) {
			mp[gethash(pam[i].id, pam[i].ed - (len1 - len2) + 1, pam[i].ed)] ++;
		}
		else mp[gethash(pam[i].id, pam[i].ed - len1 + 1, pam[i].ed)] ++;
	}
	LL ans = 0;
	for(auto i : mp) ans += 1ll * i.second * i.second;//, printf("?%d?", i.second);
	printf("%lld", ans);
	return 0;
}
/*
2
aaaa
aaa
*/

详细

Test #1:

score: 100
Accepted
time: 14ms
memory: 89764kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 17ms
memory: 89700kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 7ms
memory: 89784kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 11ms
memory: 89812kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 31ms
memory: 104896kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 35ms
memory: 105000kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 87ms
memory: 118952kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133598

result:

wrong answer 1st numbers differ - expected: '133586', found: '133598'