QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#109152 | #5440. P-P-Palindrome | Zeardoe | WA | 140ms | 77272kb | C++20 | 3.5kb | 2023-05-27 16:43:17 | 2023-05-27 16:43:19 |
Judging History
answer
/*
[templates]:
duipai
spjdp
compre
addhis
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0));
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; }
reverse(s.begin(), s.end()); cerr << s << endl;
return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
map<int, int> mp;
int base = 202009, mod = 1145141979; int powp[1000010];
struct PAM {
int cnt, lst, n; string s; int tot;
vector<int> fail; vector<array<int, 26>> ed; vector<int> len; vector<int> pre;
PAM() {
cnt = 1; lst = 1; n = 0; fail.push_back({1}); fail.push_back({1});
ed.push_back({0}); ed.push_back({0}); len.push_back(0);
len.push_back(-1); pre.push_back(0);
tot = 0;
}
int getfa(int x) {
while(s[n] != s[n - len[x] - 1]) x = fail[x];
return x;
}
int hx(int l, int r) {
return (pre[r] - pre[l - 1] * powp[r - l + 1] % mod + mod) % mod;
}
void input(int l, int leng) {
int r = l + leng - 1;
//tot += t.size();
int tt = hx(l, r); //cerr << l << " " << r << " " << s.substr(l, r - l + 1) << " " << tt << endl;
// cerr << t << endl;
if(mp.count(tt)) mp[tt] ++; else mp[tt] = 1;
}
void insert(char ch) {
n++; int p = getfa(lst); pre.push_back(((pre[n-1] * base) + s[n]) % mod);
if(!ed[p][ch - 'a']) {
++cnt; fail.push_back(0); ed.push_back({0}); len.push_back(len[p]+2);
int np = getfa(fail[p]); fail[cnt] = ed[np][ch - 'a'];
ed[p][ch - 'a'] = cnt;
if(len[cnt] % (len[cnt] - len[fail[cnt]]) == 0) {
input(n - len[cnt] + 1, len[cnt] - len[fail[cnt]]);
}
else {
input(n - len[cnt] + 1, len[cnt]);
}
}
lst = ed[p][ch - 'a']; //tot += len[lst] - len[fail[lst]];
// cerr << "n = " << n << ", lst = " << lst << ", fail[lst] = " << fail[lst] << ", delta len(T) = " << len[lst] - len[fail[lst]] << endl;
}
}pam;
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//freopen();
//freopen();
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n; cin >> n;
powp[0] = 1; for(int i = 1; i <= 1000000; i ++) powp[i] = powp[i - 1] * base % mod;
f(i, 1, n) {
pam.lst = 1; pam.n = 0; pam.pre.clear(); pam.pre.push_back(0);
cin >> pam.s; pam.s = ' ' + pam.s;
for(char ch : pam.s) if(ch != ' ') pam.insert(ch);
}
int ans = 0;
for(auto it : mp) {
ans += it.second * it.second;
}
cout << ans << endl;
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
};
详细
Test #1:
score: 100
Accepted
time: 14ms
memory: 11328kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 18ms
memory: 11276kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 8ms
memory: 11328kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 17ms
memory: 11408kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 29ms
memory: 26712kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 19ms
memory: 27376kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: -100
Wrong Answer
time: 140ms
memory: 77272kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133602
result:
wrong answer 1st numbers differ - expected: '133586', found: '133602'