QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194353 | #7512. Almost Prefix Concatenation | ucup-team296# | RE | 730ms | 205732kb | C++14 | 4.7kb | 2023-09-30 20:17:59 | 2023-09-30 20:17:59 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct sufmas {
void count_sort(vector<int> &p, vector<int> &c) {
int n = p.size();
vector<int> cnt(n);
for (auto x: c) {
cnt[x]++;
}
vector<int> p_new(n);
vector<int> pos(n);
pos[0] = 0;
for (int i = 1; i < n; i++) {
pos[i] = pos[i - 1] + cnt[i - 1];
}
for (auto x: p) {
int i = c[x];
p_new[pos[i]] = x;
pos[i]++;
}
p = p_new;
}
vector<int> p;
vector<int> c;
vector<int> lcp;
vector<vector<int>> st;
const int MAX = 20;
sufmas(string s) {
int n = s.size();
p.resize(n);
c.resize(n);
{
// k = 0
vector<pair<char, int>> a(n);
for (int i = 0; i < n; i++) a[i] = {s[i], i};
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) p[i] = a[i].second;
c[p[0]] = 0;
for (int i = 1; i < n; i++) {
if (a[i].first == a[i - 1].first) {
c[p[i]] = c[p[i - 1]];
} else {
c[p[i]] = c[p[i - 1]] + 1;
}
}
}
int k = 0;
while ((1 << k) < n) {
// k -> k + 1
for (int i = 0; i < n; i++) {
p[i] = (p[i] - (1 << k) + n) % n;
}
count_sort(p, c);
vector<int> c_new(n);
c_new[p[0]] = 0;
for (int i = 1; i < n; i++) {
pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]};
pair<int, int> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
if (now == prev) {
c_new[p[i]] = c_new[p[i - 1]];
} else {
c_new[p[i]] = c_new[p[i - 1]] + 1;
}
}
c = c_new;
k++;
}
lcp.resize(n);
k = 0;
for (int i = 0; i < n - 1; i++) {
int pi = c[i];
if (pi > 0) {
int j = p[pi - 1];
// lcp[i] = lcp(s[i..], s[j..])
while (s[i + k] == s[j + k]) k++;
}
lcp[pi] = k;
k = max(k - 1, 0);
}
st.assign(MAX, vector<int>(n));
st[0] = lcp;
for (int k = 1; k < MAX; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
int get_lcp(int i, int j) {
i = c[i];
j = c[j];
if (i > j) swap(i, j);
i++,j++;
int d = (j - i);
int k = 0;
while ((1 << (k + 1)) <= d) k++;
return min(st[k][i], st[k][j - (1 << k)]);
}
};
int mod = 998244353;
struct mint {
int value = 0;
constexpr mint() : value() {}
mint(const long &x) {
value = normalize(x);
}
static long normalize(const long &x) {
long v = x % mod;
if (v < 0) v += mod;
return v;
}
bool operator==(const mint &x) { return value == x.value; };
mint operator+(const mint &x) { return value + x.value; };
mint operator-(const mint &x) { return value - x.value; };
mint operator*(const mint &x) { return (long) value * x.value; };
void operator+=(const mint &x) { value = normalize(value + x.value); };
void operator-=(const mint &x) { value = normalize(value - x.value); };
};
int main() {
ios::sync_with_stdio(false);
string s, t;
cin >> s >> t;
int n = s.size();
int m = t.size();
string a = s + t + "#####";
sufmas sm(a);
vector<mint> d0(n + 1), d1(n + 1), d2(n + 1);
vector<mint> s0(n + 2), s1(n + 2), s2(n + 2);
d0[n] = 1;
s0[n] = 1;
for (int i = n - 1; i >= 0; i--) {
int k = sm.get_lcp(i, n);
k = min(k + 1, n - i);
if (k != n - i) {
k += sm.get_lcp(i + k, n + k);
}
k = min(k, m);
k = min(k, n - i);
mint c0 = s0[i + 1] - s0[i + 1 + k];
mint c1 = s1[i + 1] - s1[i + 1 + k];
mint c2 = s2[i + 1] - s2[i + 1 + k];
d0[i] = c0;
d1[i] = c1 + c0;
d2[i] = c2 + c1 * 2 + c0;
s0[i] = s0[i + 1] + d0[i];
s1[i] = s1[i + 1] + d1[i];
s2[i] = s2[i + 1] + d2[i];
// cout << i << " " << k << " " << d0[i].value << " " << d1[i].value<< " " << d2[i].value<< "\n";
}
cout << d2[0].value << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3436kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
75038697
result:
ok 1 number(s): "75038697"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
lvvvllvllvllvllllllllvvvllvlllvvlvlvllvlvvlvvvvlvvllllllvvlvlvvlllvvlvlvllllllvlvvvvvvlllvvvllvlvvvlvvlllvvvvvvlvlllvvvvlvvvvvlvvlvvlllvvllvvllvlvlvlvlvllllvvllvvllvlllvvvllllvvlvvllvvvvlvlvvlvvlllvvvvvvvvlvvlvlllvllvvvvllvvvlvvvvvvlvlllvllllvllllllllvvllllllvlvvlvvvlvllllvllvlvvllllllvlvvvlvlvlvvvl...
output:
538419149
result:
ok 1 number(s): "538419149"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
fzztyyyfztzzfzyztftyfzyyzzzztyyfzttzttztyzztyyyfyyftyfyfzzffyzffytttzttyzzftyfyfyftyyfzyzffyfyyzztzyyttyfyztfyfzyfzfzyftttfyyfyytzyyzfyyyzztfttzyyytzzffytyzyyyyfzfftftzzztyfftfzfzytftfttytfyzfytzfzztttttzzyztyftzzzfzfzfffttyztzfftfftyfyffztzyffttyyfyfzytytyyttfzzfyyytzzftzyyfftftyytyffzffztfytfyyyty...
output:
867833603
result:
ok 1 number(s): "867833603"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
xauxlgtqbsianlzjzglalnbtlujfrkfdqgczpmididmtamzeablrbrbjgtsdkzzcfhvcpdawqkrgdsereirlxbizhbsxlcbtgwwshekbhatqonvgupswcowythifpoubxkuoxuuisnzolzwektdcaouxbkhofvdqzmjulmhgqjxwzhgrzmorhqkgekntbzsxgvjtehfbterrhhjhqggzrqiqmcshzwpfoburpyfoehqgtitesyaekhlzcvxzdqmunyrlrhbrjoigdjzpcgptyoiowwnmqrxucxixxydurbdh...
output:
301464023
result:
ok 1 number(s): "301464023"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3880kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
816920406
result:
ok 1 number(s): "816920406"
Test #8:
score: 0
Accepted
time: 2ms
memory: 4120kb
input:
cxccxccccxccxccxcxxxccxxcxcxcxcxxcccxcxccccccxccccxccxcxcxxcxxcxcxxxcxcccxcxxxxxccxxcccxxccxxxccxccxxxxcxxccccxccxxcccxcccxxxccccxcxcxccccxxxxccxxxxxcxxxxxxcxxccxxcxcxcxxxxxcxxccxcxxxcccxcxxxccccccccxxxcccxcxxcxxxxccxxxcccccxcccxccccccxxcccxxcccxxxccxxcxccxcccxxxccxccxxxccxcxxxxccxxcxcxxcxxccxxxcxcx...
output:
206627037
result:
ok 1 number(s): "206627037"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
vmqvvbbmvmmmqqvqvmmbbvqbqvbmmbqmvvbmmmqvqvbvqqmvbbmmvmvqbvmqqbqvqqvmvmmbqvvbvmvbqmqqbqqqbqqmvvmmbvvvbvvvbmqqvbqbmvvmvqqvbqbvvvqmvvvmvqqmvqbmbvmvmqmmbmqqqbbmvqbqbbqqbmmvmmqqqvvvqqqqqmmvvvvqmvmmmmvmqmqbbvbvvqmmmqbbmvqvmvmqbqbbbmqbqbqmqbqmqbmvvqmmvbmmbvbqqvmmmbbmbbmvmmvbmqmqbbqqbqqbbqmbmmmqbqbmvbmvmmmm...
output:
460659355
result:
ok 1 number(s): "460659355"
Test #10:
score: 0
Accepted
time: 2ms
memory: 4112kb
input:
xthikaxiescbqjzrpgtcpigqjsojlsxsiowkkzsdsgscoolhdtglvpgcoggzqnnjmocvanrogbzqjcmijoukjicadaakehxgjphjgnskjvfneoyaucfadilscsucjgweuzcdfapfnrfffdowxvzkvgqzmtszjldylvehzjlvmhproaehqhuwdoadenqdrqwrlxxfouzqolwbopmkpjshczocnnsxktxozahzwqpwbmvexguvjhbvbjwsdtgaitoqwsfzkwnzgeidkamgcfhzhitfxenunlcsbsesbczvmmbu...
output:
906223232
result:
ok 1 number(s): "906223232"
Test #11:
score: 0
Accepted
time: 64ms
memory: 24284kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39285513
result:
ok 1 number(s): "39285513"
Test #12:
score: 0
Accepted
time: 68ms
memory: 24284kb
input:
hghggghghhghhgghgggghhghhhgghggghghhhhghghgggghhggggghhgghggghhhghggghghghggghggghgghhhghgggghghghgggghhhhhgghhgghhhghhghhhghhhhhhghghhgggggghghgggghghhghhgghhghhhhhhghgghhghghgggghgggggghghhhhhghhhhhhhgghhggggghhgghhhhhhhhghggggggghhghhghhghhgghhghgghhhhgghghghhhhhghggghhhhhhhgggggghgghghhhhghhgggg...
output:
58618935
result:
ok 1 number(s): "58618935"
Test #13:
score: 0
Accepted
time: 82ms
memory: 24364kb
input:
nnttcybbmnrnsuybrkmkmtumcyuyrrmbtybutunsyrkmunmncmkuknttmmtkymtcybttrmyrtckscttcksbtymtyukbbynnnbukttncmbutscbrytbrutnuyuknmtymckkttrrnsbtrkbnnnkbrccrcyybmnnybbkkbcbbccycsrcytnuucbbyytckrycktsmkymruycksrscytkskscbtbccbrurmumrkbkbttkcynmymbbmbkrksmnusryumsmmyrcsmusumbrkkbmsbyytmmruubskccsusnntcuntrrt...
output:
46252951
result:
ok 1 number(s): "46252951"
Test #14:
score: 0
Accepted
time: 75ms
memory: 24300kb
input:
ittaztseqcdirziayobnnxuzipvteycmgjbupnlxuheulnmzsdeymctprlxvkvzjwrotsauxagyrqcwzuwqyodrqsupwpyrmbwjqlvfdsrocneigxvnjfiseotxmutzwacfutqlmzmxwuqgjugwkafnxvzutgbrweqrdshwneksgxzzinnmbbioqdvbmavukaegvkpwauuoysklelsqhytlikpdpymbwhmbdmrycaiywtwjjqtecwoofyjhbumjtipwyopkuralejvopitpjcdswcvsugimgbrlibrteaqtb...
output:
838361918
result:
ok 1 number(s): "838361918"
Test #15:
score: 0
Accepted
time: 730ms
memory: 205732kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
774442405
result:
ok 1 number(s): "774442405"
Test #16:
score: -100
Runtime Error
input:
nnnddndnndnddddndnnddnddnndddndndnnndnndndndnnnddndndnddnnddnndndndnnnndndddndnndndnndddndnnddnndndnnddnnddnddndddnnnndnnndddnndnddnnnddndddnndnnndndndndnddnddnndddndddnnndddnnndnndnndnnnddnnddnndnnndnnnddnnddddnndnnddnndnnnddddnddnnndnnddddddndndnnnnndnnnndddddnddnnndddndnnddndnnnddddnndndnndndndnd...