QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479121#5440. P-P-PalindromeUESTC_DECAYALI#WA 5ms27036kbC++172.7kb2024-07-15 15:10:052024-07-15 15:10:05

Judging History

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

  • [2024-07-15 15:10:05]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:27036kb
  • [2024-07-15 15:10:05]
  • 提交

answer

#include <bits/stdc++.h>

constexpr int $n = 1'000'006;

namespace HL666 {
	const int mod1=998244853,mod2=1e9+9;
	struct Hasher
	{
		int x,y;
		inline Hasher(const int& X=0,const int& Y=0)
		{
			x=X; y=Y;
		}
		inline int64_t val(void)
		{
			return ((1LL*x)<<31LL)|(1LL*y);
		}
		friend inline bool operator == (const Hasher& A,const Hasher& B)
		{
			return A.x==B.x&&A.y==B.y;
		}
		friend inline Hasher operator + (const Hasher& A,const Hasher& B)
		{
			return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
		}
		friend inline Hasher operator - (const Hasher& A,const Hasher& B)
		{
			return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
		}
		friend inline Hasher operator * (const Hasher& A,const Hasher& B)
		{
			return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
		}
	}h[$n],pw[$n];
	const Hasher seed=Hasher(67,133);
	void build_hash(const char *s, int n) {
		pw[0]=Hasher(1,1);
		for (int i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
		for (int i=1;i<=n;++i) h[i]=h[i-1]*seed+Hasher(s[i],s[i]);
	}
	
	int64_t get_hash(int l, int r) {
		return (h[r]-h[l-1]*pw[r-l+1]).val();
	}
}

namespace PAM {
	int go[$n][26], len[$n], fail[$n], las, O;
	char s[$n], s_len;
	
	void init() {
		scanf("%s", s + 1); s_len = strlen(s + 1);
		HL666::build_hash(s, s_len);
		len[0] = -1; len[1] = 0; fail[1] = 0;
		memset(go[0], 0, sizeof(go[0]));
		memset(go[1], 0, sizeof(go[1]));
		las = 1, O = 1;
		s[0] = 1;
	}
	
	void insert(int i) {
		int u = s[i] - 'a';
		int p = las;
		while(p && s[i - len[p] - 1] != s[i]) p = fail[p];
		if(go[p][u]) { las = go[p][u]; return ; }
		int np = las = go[p][u] = ++O;
		memset(go[np], 0, sizeof(go[np]));
		
		len[np] = len[p] + 2;
		if(!p) return fail[np] = 1, void(0);
		do p = fail[p]; while(p && s[i - len[p] - 1] != s[i]);
		if(go[p][u]) fail[np] = go[p][u];
		else fail[np] = 1;
		return ;
	}
} // namespace PAM

inline void chkmx(int64_t &a, int64_t b) {
	if(b > a) a = b;
}

int main() {
	int n; scanf("%d", &n);
	std::map<int64_t, int64_t> hkr;
	while(n--) {
		using namespace PAM;
		init();
		for(int i = 1; i <= s_len; ++i) {
			insert(i);
			if(len[las] <= 0) continue;
			int per = len[las] - len[fail[las]];
			int L = (len[las] % per == 0 ? per : len[las]);
			// std::cout << "(" << len[las] << ", " << L << ", get_hash(" << i - L + 1 << ", " << i << ") = " << HL666::get_hash(i - L + 1, i) << ")" << char(i == s_len ? 10 : 32);
			chkmx(hkr[HL666::get_hash(i - L + 1, i)], len[las] / L);
		}
	}
	int64_t ans = 0;
	for(auto [k, v]: hkr) ans += v * v;// std::cout << "k = " << (k >> 32) << char(10);
	printf("%lld\n", ans); 
	return 0;
}

/*
2
aaaa
aaa

3
abaaa
abbbba
bbbaba
*/

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 27036kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

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

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 0ms
memory: 24164kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 0ms
memory: 24140kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

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

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

9216

result:

wrong answer 1st numbers differ - expected: '3600000000', found: '9216'