QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#278916 | #7876. Cyclic Substrings | ucup-team173# | WA | 112ms | 253952kb | C++17 | 4.2kb | 2023-12-07 22:53:48 | 2023-12-07 22:53:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
constexpr int P1 = 998244353, P2 = 1e9 + 7, b1 = 231, b2 = 13131, N = 20000100;
pii pw[N]; multiset<pii> st[2000100];
void solve() {
int n; string s;
cin >> n >> s;
s = ' ' + s + s + s;
pw[0] = Mp(1, 1);
for(int i = 1; i < N; i++) {
pw[i] = Mp( 1ll * pw[i - 1].fi * b1 % P1,
1ll * pw[i - 1].se * b2 % P2);
}
vector<pii> hsh; hsh.pb(Mp(0, 0));
auto push = [&](vector<pii> &h, char ch) {
auto [a, b] = h.back();
hsh.pb(Mp( (1ll * a * b1 + ch) % P1,
(1ll * b * b2 + ch) % P2));
};
auto get = [&](vector<pii> &h, int l, int r) -> pii {
auto L = h[l - 1], R = h[r];
int len = r - l + 1;
return Mp( (R.fi - 1ll * L.fi * pw[len].fi % P1 + P1) % P1,
(R.se - 1ll * L.se * pw[len].se % P2 + P2) % P2);
};
string t = "-$";
for(int i = 1; i <= 3 * n; i++) {
t += s[i];
t += '#';
}
t.pop_back(), t += "@";
for(int i = 1; i < SZ(t); i++) {
push(hsh, t[i]);
}
// cout << "f" << endl;
vi r(4 * n + 2), fr(4 * n + 2), frlen(4 * n + 2);
for(int i = 1, rmx = 0, center = 0; i <= 4 * n; i++) {
if(i <= rmx) {
r[i] = min(r[2 * center - i], rmx - i + 1);
if(2 * center - i >= 2 * n + 1)
fr[i] = 2 * center - i, frlen[i] = r[i];
}
while(i - r[i] > 0 && i + r[i] < SZ(t) && t[i - r[i]] == t[i + r[i]]) r[i]++;
if(i + r[i] - 1 > rmx) rmx = i + r[i] - 1, center = i;
}
// cout << "f" << endl;
// for(int i = 2 * n + 1; i <= 4 * n; i++) {
// cout << fr[i] << ' ' << frlen[i] << endl;
// }
// t = -$0#1#0#1#0#_0#1#0#1#0_20_#0#1#0#1#0@
vi cnt(4 * n + 2);
map<pair<pii, int>, int> mp;
for(int i = 4 * n; i >= 2 * n + 1; i--) {
cnt[i]++;
if(i & 1) { // even length
while(r[i] > frlen[i]) {
while(SZ(st[i]) && -st[i].begin()->fi == r[i]) {
cnt[i] += st[i].begin()->se;
st[i].erase(st[i].begin());
}
if(r[i] % 2 == 0 && r[i] <= n) {
auto h = get(hsh, i - r[i] + 1, i + r[i] - 1);
mp[Mp(h, r[i])] += cnt[i];
// cout << i - r[i] + 1 << ' ' << i + r[i] - 1 << ' ' << r[i] << ' ' << cnt[i] << " " << h.fi << ' ' << h.se << endl;
}
r[i]--;
}
} else {
while(r[i] > frlen[i]) {
while(SZ(st[i]) && -st[i].begin()->fi == r[i]) {
cnt[i] += st[i].begin()->se;
st[i].erase(st[i].begin());
}
if(r[i] % 2 != 0 && r[i] <= n) {
auto h = get(hsh, i - r[i] + 1, i + r[i] - 1);
// cout << i - r[i] + 1 << ' ' << i + r[i] - 1 << ' ' << r[i] << ' ' << cnt[i] << " " << h.fi << ' ' << h.se << endl;
mp[Mp(h, r[i])] += cnt[i];
}
r[i]--;
}
}
auto merge = [&](multiset<pii> &st1, multiset<pii> &st2) {
if(SZ(st1) < SZ(st2)) swap(st1, st2);
for(auto o : st2) st1.insert(o);
};
if(fr[i]) {
// assert(0 <= fr[i] - 2 * n && fr[i] - 2 * n < 2000100);
// assert(0 <= i - 2 * n && i - 2 * n < 2000100);
merge(st[fr[i] - 2 * n], st[i - 2 * n]);
st[fr[i] - 2 * n].insert(Mp(-frlen[i], cnt[i]));
}
}
// cout << "f" << endl;
ll ans = 0;
for(auto [p, c] : mp) {
int len = p.se;
// cout << len << ' ' << c << '\n';
ans += 1ll * c * c * len;
}
cout << ans << '\n';
}
signed main() {
// freopen("data.in", "r", stdin);
atexit([]{cerr << 1. * clock() / CLOCKS_PER_SEC << "s\n";});
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 112ms
memory: 253952kb
input:
5 01010
output:
22
result:
wrong answer 1st numbers differ - expected: '39', found: '22'