QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#549709 | #5440. P-P-Palindrome | yueyuey | WA | 24ms | 264624kb | C++14 | 2.8kb | 2024-09-06 19:58:43 | 2024-09-06 19:58:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define int long long
#define lowbit(x) (x&(-x))
#define pll pair<int,int>
const int N = 1e6+10;
const int mod = 998244353;
const ld eps = 1e-6;
int dx[] = {-1,1,0,0,-1,-1,1,1};
int dy[] = {0,0,-1,1,-1,1,-1,1};
int n,m;
int tr[N][28];
int fail[N],len[N],cnt[N];
int idx,last;
string s;
const int P1 = 998244353, BASE1 = 131;
const int P2 = 1000000007, BASE2 = 13331;
int B1[N],B2[N];
struct Hash{
long long a1,a2;
bool operator==(const Hash &b) const{
return a1 == b.a1 && a2 == b.a2;
}
bool operator<(const Hash &b) const{
return a1 == b.a1 ? a2 < b.a2 : a1 < b.a1;
}
Hash operator+(const int b) const{
return { (a1 * BASE1 + b) % P1, (a2 *BASE2 + b) % P2 };
}
Hash operator<<(const int b) const{
return { a1 * B1[b] % P1, a2 * B2[b] % P2 };
}
Hash operator-(const Hash &b) const{
return { (a1 - b.a1 + P1) % P1, (a2 - b.a2 + P2) % P2 };
}
}h[N],H[N];
Hash get(int l,int r){
return h[r] - (h[l-1] << (r - l + 1));
}
map<Hash,int> ma;
void init(){
memset(fail,0,sizeof(fail));
memset(tr,0,sizeof(tr));
memset(len,0,sizeof(len));
memset(cnt,0,sizeof(cnt));
fail[0] = 1; fail[1] = 0;
len[0] = 0; len[1] = -1;
idx = 1;
B1[0] = 1;
B2[0] = 1;
for(int i=1;i<N;i++){
B1[i] = 1ll * B1[i-1] * BASE1 % P1;
B2[i] = 1ll * B2[i-1] * BASE2 % P2;
}
}
int getfail(int x,int pos){
while(pos-len[x]-1<=0||s[pos-len[x]-1]!=s[pos]) x = fail[x];
return x;
}
void insert(char ch,int pos){
int x = ch - 'a';
int u = getfail(last,pos);
if(!tr[u][x]){
fail[++idx] = tr[getfail(fail[u],pos)][x];
tr[u][x] = idx;
len[idx] = len[u] + 2;
int k = len[idx] - len[fail[idx]];
Hash hash;
if(len[idx]%k==0){
hash = get(pos-k+1,pos);
ma[hash] = max(ma[hash],len[idx]/k);
}else{
hash = h[len[idx]];
ma[hash] = max(ma[hash],1ll);
}
}
last = tr[u][x];
}
void solve(){
cin>>n;
init();
for(int i=1;i<=n;i++){
cin>>s;
int siz = s.length();
s = " " + s;
last = 0;
h[0].a1 = 0;
h[0].a2 = 0;
for(int j=1;j<=siz;j++) h[j] = h[j-1] + s[j];
for(int j=1;j<=siz;j++){
insert(s[j],j);
}
}
int ans = 0;
for(auto i : ma){
ans += i.second * i.second;
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
// cin>>T;
while(T--){
solve();
}
return 0;
}
/*
/\_/\
(= ._.)
/ > \>
*/
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 264400kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 15ms
memory: 264624kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 19ms
memory: 263872kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 24ms
memory: 263536kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1281
result:
wrong answer 1st numbers differ - expected: '1282', found: '1281'