QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194353#7512. Almost Prefix Concatenationucup-team296#RE 730ms205732kbC++144.7kb2023-09-30 20:17:592023-09-30 20:17:59

Judging History

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

  • [2023-09-30 20:17:59]
  • 评测
  • 测评结果:RE
  • 用时:730ms
  • 内存:205732kb
  • [2023-09-30 20:17:59]
  • 提交

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...

output:


result: