QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253987 | #7512. Almost Prefix Concatenation | LeticiaFCS | WA | 1ms | 3860kb | C++20 | 3.1kb | 2023-11-17 21:29:15 | 2023-11-17 21:29:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
/**
* Author: Chris
* Description: Find $x$ such that $ax \equiv 1$(mod $m$). The inverse
* only exist if $a$ and $m$ are coprimes.
*/
int minv(int a, int m) {
a %= m; assert(a);
return a == 1 ? 1 : int(m - int64_t(minv(m, a)) * m / a);
}
using pii = pair<int, int>;
using lint = int64_t;
constexpr int mod(lint x, int m){
x %= m;
x += m;
return x % m;
}
struct hash_t{
string s;
int n;
const int b = 31, m1 = 1000000007, m2 = 998244353;
vector<int> h1, h2, p1, p2;
hash_t(string _s) : s(_s), n(int(_s.size())), h1(n+1), h2(n+1), p1(n+1, 1), p2(n+1, 1){
int b1 = 1, b2 = 1;
for(int i = 1; i<=n; i++){
int x = int(s[i-1]-'a') + 1;
h1[i] = mod(h1[i-1] * b + x, m1);
h2[i] = mod(h2[i-1] * b + x, m2);
b1 = mod(b1 * b, m1);
p1[i] = mod(p1[i-1] * b, m1);
b2 = mod(b2 * b, m2);
p2[i] = mod(p2[i-1] * b, m2);
}
}
pii get(int l, int r){ // [l, r[
int a = mod(h1[r] - h1[l] * p1[r-l], m1);
int b = mod(h2[r] - h2[l] * p2[r-l], m2);
return {a, b};
}
};
const int MOD = 998244353;
template<typename T> struct FT { // 8b7639
vector<T> s;
FT(int n) : s(n) {}
FT(const vector<T>& A) : s(A) {
const int N = int(s.size());
for (int a = 0; a < N; ++a)
if ((a | (a + 1)) < N) s[a | (a + 1)] = mod(s[a | (a + 1)] + s[a], MOD);
}
void update(int pos, T dif) { // a[pos] += dif
for (; pos < (int)s.size(); pos |= pos + 1) s[pos] = mod(s[pos] + dif, MOD);
}
T query(int pos) { // sum of values in [0, pos)
T res = 0;
for (; pos > 0; pos &= pos - 1) res = mod(res + s[pos-1], MOD);
return res;
}
T query(int a, int b) { // sum of values in [0, pos)
return query(b) - query(a);
}
};
int main(){
cin.tie(0)->sync_with_stdio(false);
string a, b;
cin>>a>>b;
int n = int(a.size()), m = int(b.size());
a += '!';
b += '?';
hash_t ha(a), hb(b);
auto getend = [&](int start){ //[start, end[
int l = 0, r = min(m, n - start);
int startb = 0;
while(l + 1 < r){
int mid = (l+r) / 2;
if(ha.get(start, start + mid) == hb.get(startb, startb + mid)) l = mid;
else r = mid;
}
start += r;
startb += r;
l = 0, r = min(m - startb, n - start) + 1;
while(l + 1 < r){
int mid = (l+r) / 2;
if(ha.get(start, start + mid) == hb.get(startb, startb + mid)) l = mid;
else r = mid;
}
start += r;
return start;
};
vector<int> r(n);
for(int i = 0; i < n; i++) r[i] = getend(i);
FT<lint> sn2(n+1), sn(n+1), qtd(n+1);
qtd.update(n, 1);
for(int i = n-1; i >= 0; i--){
lint SN2 = sn2.query(i, r[i]);
lint SN = sn.query(i, r[i]);
lint Q = qtd.query(i, r[i]);
sn2.update(i, mod(SN2 + 2* SN + Q, MOD));
sn.update(i, SN + Q);
qtd.update(i, Q);
}
cout<<sn2.query(1)<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3860kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
435527325
result:
wrong answer 1st numbers differ - expected: '75038697', found: '435527325'