QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253987#7512. Almost Prefix ConcatenationLeticiaFCSWA 1ms3860kbC++203.1kb2023-11-17 21:29:152023-11-17 21:29:16

Judging History

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

  • [2023-11-17 21:29:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2023-11-17 21:29:15]
  • 提交

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'