QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#248810#7512. Almost Prefix ConcatenationUFRJ#WA 127ms40660kbC++204.2kb2023-11-11 21:56:092023-11-11 21:56:10

Judging History

你现在查看的是最新测评结果

  • [2023-11-11 21:56:10]
  • 评测
  • 测评结果:WA
  • 用时:127ms
  • 内存:40660kb
  • [2023-11-11 21:56:09]
  • 提交

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'