QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398240#5440. P-P-PalindromenKessiWA 71ms122984kbC++142.7kb2024-04-25 09:27:012024-04-25 09:27:02

Judging History

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

  • [2024-04-25 09:27:02]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:122984kb
  • [2024-04-25 09:27:01]
  • 提交

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;
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];
uLL P[MAXN];
vector <uLL> Hash[MAXN];
map <uLL, 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);
}
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;
	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;
		}
	}
	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: 11ms
memory: 93356kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 8ms
memory: 92808kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 22ms
memory: 92596kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 8ms
memory: 92732kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

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

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 16ms
memory: 108184kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0
Accepted
time: 71ms
memory: 121676kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

score: 0
Accepted
time: 67ms
memory: 118832kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

score: 0
Accepted
time: 64ms
memory: 117120kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

score: 0
Accepted
time: 65ms
memory: 118140kb

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

score: 0
Accepted
time: 70ms
memory: 122984kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

score: 0
Accepted
time: 24ms
memory: 94728kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

6

result:

ok 1 number(s): "6"

Test #13:

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

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

6

result:

ok 1 number(s): "6"

Test #14:

score: 0
Accepted
time: 15ms
memory: 95876kb

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

6

result:

ok 1 number(s): "6"

Test #15:

score: -100
Wrong Answer
time: 27ms
memory: 111128kb

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

201946

result:

wrong answer 1st numbers differ - expected: '113382', found: '201946'