QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#248810 | #7512. Almost Prefix Concatenation | UFRJ# | WA | 127ms | 40660kb | C++20 | 4.2kb | 2023-11-11 21:56:09 | 2023-11-11 21:56:10 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using lint = int64_t;
int minv(int a, int m) {
a %= m; assert(a);
return a == 1 ? 1 : int(m - int64_t(minv(m, a)) * m / a);
}
template<unsigned M_> struct modnum {
static constexpr unsigned M = M_;
using ll = int64_t; using ull = uint64_t; unsigned x;
modnum& norm(unsigned a) { x = a < M ? a : a - M; return *this; }
constexpr modnum(ll a = 0U) : x(unsigned((a %= ll(M)) < 0 ? a + ll(M) : a)) {}
explicit operator int() const { return x; }
modnum& operator+=(const modnum &a) {return norm(x + a.x); }
modnum& operator-=(const modnum &a) {return norm(x - a.x + M); }
modnum& operator*=(const modnum &a) { x = unsigned(ull(x) * a.x % M); return *this; }
modnum& operator/=(const modnum &a) { return (*this *= a.inv()); }
modnum operator+ (const modnum &a) const { return (modnum(*this) += a); }
modnum operator- (const modnum &a) const { return (modnum(*this) -= a); }
modnum operator* (const modnum &a) const { return (modnum(*this) *= a); }
modnum operator/ (const modnum &a) const { return (modnum(*this) /= a); }
template<typename T> friend modnum operator+(T a, const modnum &b) { return (modnum(a) += b); }
template<typename T> friend modnum operator-(T a, const modnum &b) { return (modnum(a) -= b); }
template<typename T> friend modnum operator*(T a, const modnum &b) { return (modnum(a) *= b); }
template<typename T> friend modnum operator/(T a, const modnum &b) { return (modnum(a) /= b); }
modnum operator+() const {return *this; }
modnum operator-() const {return modnum() - *this; }
modnum pow(ll e) const {
if(e < 0) return inv().pow(-e);
modnum b = x, xe = 1U;
for(; e; e >>= 1) { if(e & 1) xe *= b; b *= b; }
return xe;
}
modnum inv() const {return minv(x, M); }
friend modnum inv(const modnum &a) { return a.inv(); }
explicit operator bool() const { return x; }
friend bool operator==(const modnum &a, const modnum &b) {
return a.x == b.x;
}
friend bool operator!=(const modnum &a, const modnum &b) {
return a.x != b.x;
}
friend ostream &operator<<(ostream &os, const modnum &a) {
return os << a.x;
}
friend istream &operator>>(istream &in, modnum &n) {
ll v_;
in >> v_;
n = modnum(v_);
return in;
}
};
const int mod = 998244353;
using num = modnum<mod>;
const int b = 31;
using hnum = modnum<int(1e9) + 7>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string s, t;
cin>>s>>t;
int n = int(s.size()), m = int(t.size());
vector<hnum>hs(n + 1), ht(m + 1), pot(m + 1); pot[0] = 1;
for(int i=0;i<n;i++) hs[i+1] = hs[i] * b + (s[i] - 'a' + 1);
for(int i=0;i<m;i++) ht[i+1] = ht[i] * b + (t[i] - 'a' + 1);
for(int i=0;i<m;i++) pot[i+1] = pot[i] * b;
vector<num>cnt(n + 1), sum(n + 1), ans(n + 1);
vector<num>suf_cnt(n + 2), suf_sum(n + 2), suf_ans(n + 2);
cnt[n] = suf_cnt[n] = 1;
for(int i=n-1;i>=0;i--){
int lo = 1, hi = min(n - i, m);
while(lo <= hi){
int mid = (lo + hi) >> 1;
auto S = hs[i + mid] - hs[i] * pot[mid];
auto T = ht[mid];
if(S == T) lo = mid + 1;
else hi = mid - 1;
}
int j = i + hi;
if(j < n) j++;
int x = j - i;
if(j < n){
lo = 1, hi = min(n - j, m);
while(lo <= hi){
int mid = (lo + hi) >> 1;
auto S = hs[j + mid] - hs[j] * pot[mid];
auto T = ht[x + mid] - ht[x] * pot[mid];
if(S == T) lo = mid + 1;
else hi = mid - 1;
}
j = j + hi;
}
j = min(j, i + m);
cnt[i] = suf_cnt[i+1] - suf_cnt[j+1];
sum[i] = suf_sum[i+1] - suf_sum[j+1] + cnt[i];
ans[i] = suf_ans[i+1] - suf_ans[j+1] +
2 * (suf_sum[i+1] - suf_sum[j+1]) + cnt[i];
suf_cnt[i] = suf_cnt[i+1] + cnt[i];
suf_sum[i] = suf_sum[i+1] + sum[i];
suf_ans[i] = suf_ans[i+1] + ans[i];
}
cout<<ans[0]<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
75038697
result:
ok 1 number(s): "75038697"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
lvvvllvllvllvllllllllvvvllvlllvvlvlvllvlvvlvvvvlvvllllllvvlvlvvlllvvlvlvllllllvlvvvvvvlllvvvllvlvvvlvvlllvvvvvvlvlllvvvvlvvvvvlvvlvvlllvvllvvllvlvlvlvlvllllvvllvvllvlllvvvllllvvlvvllvvvvlvlvvlvvlllvvvvvvvvlvvlvlllvllvvvvllvvvlvvvvvvlvlllvllllvllllllllvvllllllvlvvlvvvlvllllvllvlvvllllllvlvvvlvlvlvvvl...
output:
538419149
result:
ok 1 number(s): "538419149"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
fzztyyyfztzzfzyztftyfzyyzzzztyyfzttzttztyzztyyyfyyftyfyfzzffyzffytttzttyzzftyfyfyftyyfzyzffyfyyzztzyyttyfyztfyfzyfzfzyftttfyyfyytzyyzfyyyzztfttzyyytzzffytyzyyyyfzfftftzzztyfftfzfzytftfttytfyzfytzfzztttttzzyztyftzzzfzfzfffttyztzfftfftyfyffztzyffttyyfyfzytytyyttfzzfyyytzzftzyyfftftyytyffzffztfytfyyyty...
output:
867833603
result:
ok 1 number(s): "867833603"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
xauxlgtqbsianlzjzglalnbtlujfrkfdqgczpmididmtamzeablrbrbjgtsdkzzcfhvcpdawqkrgdsereirlxbizhbsxlcbtgwwshekbhatqonvgupswcowythifpoubxkuoxuuisnzolzwektdcaouxbkhofvdqzmjulmhgqjxwzhgrzmorhqkgekntbzsxgvjtehfbterrhhjhqggzrqiqmcshzwpfoburpyfoehqgtitesyaekhlzcvxzdqmunyrlrhbrjoigdjzpcgptyoiowwnmqrxucxixxydurbdh...
output:
301464023
result:
ok 1 number(s): "301464023"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
816920406
result:
ok 1 number(s): "816920406"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
cxccxccccxccxccxcxxxccxxcxcxcxcxxcccxcxccccccxccccxccxcxcxxcxxcxcxxxcxcccxcxxxxxccxxcccxxccxxxccxccxxxxcxxccccxccxxcccxcccxxxccccxcxcxccccxxxxccxxxxxcxxxxxxcxxccxxcxcxcxxxxxcxxccxcxxxcccxcxxxccccccccxxxcccxcxxcxxxxccxxxcccccxcccxccccccxxcccxxcccxxxccxxcxccxcccxxxccxccxxxccxcxxxxccxxcxcxxcxxccxxxcxcx...
output:
206627037
result:
ok 1 number(s): "206627037"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
vmqvvbbmvmmmqqvqvmmbbvqbqvbmmbqmvvbmmmqvqvbvqqmvbbmmvmvqbvmqqbqvqqvmvmmbqvvbvmvbqmqqbqqqbqqmvvmmbvvvbvvvbmqqvbqbmvvmvqqvbqbvvvqmvvvmvqqmvqbmbvmvmqmmbmqqqbbmvqbqbbqqbmmvmmqqqvvvqqqqqmmvvvvqmvmmmmvmqmqbbvbvvqmmmqbbmvqvmvmqbqbbbmqbqbqmqbqmqbmvvqmmvbmmbvbqqvmmmbbmbbmvmmvbmqmqbbqqbqqbbqmbmmmqbqbmvbmvmmmm...
output:
460659355
result:
ok 1 number(s): "460659355"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
xthikaxiescbqjzrpgtcpigqjsojlsxsiowkkzsdsgscoolhdtglvpgcoggzqnnjmocvanrogbzqjcmijoukjicadaakehxgjphjgnskjvfneoyaucfadilscsucjgweuzcdfapfnrfffdowxvzkvgqzmtszjldylvehzjlvmhproaehqhuwdoadenqdrqwrlxxfouzqolwbopmkpjshczocnnsxktxozahzwqpwbmvexguvjhbvbjwsdtgaitoqwsfzkwnzgeidkamgcfhzhitfxenunlcsbsesbczvmmbu...
output:
906223232
result:
ok 1 number(s): "906223232"
Test #11:
score: 0
Accepted
time: 4ms
memory: 7088kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39285513
result:
ok 1 number(s): "39285513"
Test #12:
score: 0
Accepted
time: 6ms
memory: 7008kb
input:
hghggghghhghhgghgggghhghhhgghggghghhhhghghgggghhggggghhgghggghhhghggghghghggghggghgghhhghgggghghghgggghhhhhgghhgghhhghhghhhghhhhhhghghhgggggghghgggghghhghhgghhghhhhhhghgghhghghgggghgggggghghhhhhghhhhhhhgghhggggghhgghhhhhhhhghggggggghhghhghhghhgghhghgghhhhgghghghhhhhghggghhhhhhhgggggghgghghhhhghhgggg...
output:
58618935
result:
ok 1 number(s): "58618935"
Test #13:
score: 0
Accepted
time: 9ms
memory: 6932kb
input:
nnttcybbmnrnsuybrkmkmtumcyuyrrmbtybutunsyrkmunmncmkuknttmmtkymtcybttrmyrtckscttcksbtymtyukbbynnnbukttncmbutscbrytbrutnuyuknmtymckkttrrnsbtrkbnnnkbrccrcyybmnnybbkkbcbbccycsrcytnuucbbyytckrycktsmkymruycksrscytkskscbtbccbrurmumrkbkbttkcynmymbbmbkrksmnusryumsmmyrcsmusumbrkkbmsbyytmmruubskccsusnntcuntrrt...
output:
46252951
result:
ok 1 number(s): "46252951"
Test #14:
score: 0
Accepted
time: 9ms
memory: 7072kb
input:
ittaztseqcdirziayobnnxuzipvteycmgjbupnlxuheulnmzsdeymctprlxvkvzjwrotsauxagyrqcwzuwqyodrqsupwpyrmbwjqlvfdsrocneigxvnjfiseotxmutzwacfutqlmzmxwuqgjugwkafnxvzutgbrweqrdshwneksgxzzinnmbbioqdvbmavukaegvkpwauuoysklelsqhytlikpdpymbwhmbdmrycaiywtwjjqtecwoofyjhbumjtipwyopkuralejvopitpjcdswcvsugimgbrlibrteaqtb...
output:
838361918
result:
ok 1 number(s): "838361918"
Test #15:
score: 0
Accepted
time: 72ms
memory: 39948kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
774442405
result:
ok 1 number(s): "774442405"
Test #16:
score: 0
Accepted
time: 120ms
memory: 38764kb
input:
nnnddndnndnddddndnnddnddnndddndndnnndnndndndnnnddndndnddnnddnndndndnnnndndddndnndndnndddndnnddnndndnnddnnddnddndddnnnndnnndddnndnddnnnddndddnndnnndndndndnddnddnndddndddnnndddnnndnndnndnnnddnnddnndnnndnnnddnnddddnndnnddnndnnnddddnddnnndnnddddddndndnnnnndnnnndddddnddnnndddndnnddndnnnddddnndndnndndndnd...
output:
478212008
result:
ok 1 number(s): "478212008"
Test #17:
score: 0
Accepted
time: 118ms
memory: 40500kb
input:
ievnetxypatirsocqrmgmhfxnkgzrscclietylohbcshjjxfmqhlxvebythkwllhjxwjngxbjeivttdgjttmyqgxsqotxueuvzrslcqpranaucprjmfczshtoqggczmbuwixllhnlcjhrvfixisvqdlxxmevucbvzolweshgvxeocppggthqkljyiszeqkpnybogisosqzdasfqgpuzudnnabwoqtrpxllqkxlbwsexwduvutufncthrmywlsqlccetggdflmgewzvhsmpyznzsxcftkoyfhgmgvliwxbywi...
output:
702291108
result:
ok 1 number(s): "702291108"
Test #18:
score: 0
Accepted
time: 68ms
memory: 40660kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
301945039
result:
ok 1 number(s): "301945039"
Test #19:
score: 0
Accepted
time: 127ms
memory: 40552kb
input:
gggggcgcgggcgccgggcgcccgccccggcccgcggccccggcccccggccgccccccggcccgggcccgggggcccgggggcgggccgcccccccgcgcggggggggggcggggggcggccgcccggggccgccccgcgcgggcggggccgcgcggcggccgggccgccgcggcccgcccggcgccgccgggcgggggcggggccgccgcccccgccccccgggggcgcgcgccggccggcggcggggcgccggcgccccggccgggggccgccccccccgcggcgcggggggcgccc...
output:
602912498
result:
ok 1 number(s): "602912498"
Test #20:
score: 0
Accepted
time: 119ms
memory: 40408kb
input:
zdomsivxdzqlpexdauxxrjvembwqtchcxcpboqwmilagfpnrzyicztptfvdlqehajqoxcqvtoglsusgfioxtwheivlmgapepuoevghzmdadbkkkrdusnvxmansofunrgmppyktkxcottuiolirqlsflpnkghhxngutoovfzluiboooswqknpedyiaspikpveswjqnqitfbynjgiqymkrldekgmkavalduxlscjewmpoctbxjujtxlavpibkyerspcfchiticgjsvmzvtadhimnvacljbhmzikeabhjoszfig...
output:
435002470
result:
ok 1 number(s): "435002470"
Test #21:
score: 0
Accepted
time: 121ms
memory: 37884kb
input:
aabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaab...
output:
571187577
result:
ok 1 number(s): "571187577"
Test #22:
score: -100
Wrong Answer
time: 114ms
memory: 38920kb
input:
abacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacab...
output:
516925170
result:
wrong answer 1st numbers differ - expected: '785945100', found: '516925170'