QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#479121 | #5440. P-P-Palindrome | UESTC_DECAYALI# | WA | 5ms | 27036kb | C++17 | 2.7kb | 2024-07-15 15:10:05 | 2024-07-15 15:10:05 |
Judging History
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'