QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466669#8512. Harmonic OperationsSwarthmore#WA 8ms19704kbC++205.9kb2024-07-08 01:18:012024-07-08 01:18:02

Judging History

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

  • [2024-07-08 01:18:02]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:19704kb
  • [2024-07-08 01:18:01]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const char nl = '\n';

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

using cd = complex<double>;
const double PI = acos(-1);

#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(1259);

int reverse(int num, int lg_n) {
    int res = 0;
    for (int i = 0; i < lg_n; i++) {
        if (num & (1 << i))
            res |= 1 << (lg_n - 1 - i);
    }
    return res;
}

void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    int lg_n = 0;
    while ((1 << lg_n) < n)
        lg_n++;

    for (int i = 0; i < n; i++) {
        if (i < reverse(i, lg_n))
            swap(a[i], a[reverse(i, lg_n)]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}
vector<ll> multiply(vector<ll> const& a, vector<ll> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<ll> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

const int MX = 1000010;

ll base1[MX], base2[MX];
int base;
const int MOD = 1000000007;

const ll p1 = MOD;
const ll p2 = MOD+2;

// If you don't need to query arbitrary ranges,
// only maintain val1 and val2 to save space.
// get() = val1 * p2 + val2
struct hsh {
    ll val1, val2;
    vl val1s, val2s;
    vl nums;
    hsh() {
        val1 = 0;
        val2 = 0;
        val1s.pb(0);
        val2s.pb(0);
    }

    void push_back(ll v) {
        v++;
        val1 *= base; val1 += v; val1 %= p1;
        val2 *= base; val2 += v; val2 %= p2;

        val1s.pb(val1);
        val2s.pb(val2);
        nums.pb(v);
    }

    ll get(int L, int R) {
        ll A = (val1s[R+1] - (val1s[L] * base1[R-L+1]) % p1 + p1) % p1;
        ll B = (val2s[R+1] - (val2s[L] * base2[R-L+1]) % p2 + p2) % p2;
        return A*p2+B;
    }
};

void prepHash() {
    base = uid(MOD/5, MOD/2);

    base1[0] = 1; base2[0] = 1;
    FOR(i, 1, MX) {
        base1[i] = (base1[i-1] * base) % p1;
        base2[i] = (base2[i-1] * base) % p2;
    }
}



void solve() {
    prepHash();

    string S; cin >> S;
    int N = sz(S);
    hsh H;
    F0R(iter, 2) {
        trav(a, S) {
            H.pb(a-'a');
        }
    }
    hsh Hr;
    F0R(iter, 2) {
        F0Rd(i, sz(S)) {
            Hr.pb(S[i]-'a');
        }
    }

    bool ok[2][N];
    F0R(i, N) {
        ok[0][i] = H.get(i, i+N-1) == H.get(0, N-1);
        ok[1][i] = Hr.get(i, i+N-1) == H.get(0, N-1);
    }

    int K; cin >> K;
    vl sums(N), negSums(N), revSums(N), negRevSums(N);
    bool fl = false;
    int cur = 0;
    sums[0]++; negSums[0]++;
    F0R(i, K) {
        char C; cin >> C;
        if (C != 'I') {
            int X; cin >> X;
            if (C == 'R') X = N-X;
            cur += X; cur %= N;
        } else fl = !fl;
        if (fl) {
            revSums[cur]++;
            negRevSums[(N-cur)%N]++;
        } else {
            sums[cur]++;
            negSums[(N-cur)%N]++;
        }
    }


    vl poly1 = multiply(negSums, sums);
    dbg(sums, negSums, poly1);
    ll ans = 0;
    F0R(i, sz(poly1)) {
        if (ok[0][i%N]) ans += poly1[i];
    }
    vl poly2 = multiply(revSums, sums);
    F0R(i, sz(poly2)) {
        if (ok[1][i%N]) ans += poly2[i] * 2;
    }
    vl poly3 = multiply(revSums, negRevSums);
    F0R(i, sz(poly3)) {
        if (ok[0][i%N]) ans +=  poly3[i];
    }
    ans -= K+1;
    ans /= 2;
    cout << ans << nl;

}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 19660kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 3ms
memory: 19668kb

input:

aaa
4
R 1
I
I
R 1

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 6ms
memory: 19668kb

input:

caso
6
L 1
I
I
R 1
I
I

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 8ms
memory: 19468kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
100
L 12
I
R 47
L 54
I
I
R 80
L 86
L 19
R 5
L 53
L 40
R 20
L 11
R 40
I
I
R 66
R 6
L 76
L 93
R 39
I
I
L 24
R 59
R 99
L 52
I
I
R 77
L 11
R 60
L 16
I
L 40
I
R 35
L 64
R 11
L 34
I
R 35
I
L 87
I
I
L 42
L ...

output:

5050

result:

ok 1 number(s): "5050"

Test #5:

score: 0
Accepted
time: 7ms
memory: 19704kb

input:

wewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewe
100
R 83
R 34
I
I
R 87
R 74
L 98
I
L 77
L 8
R 23
L 94
I
I
L 79
L 87
L 47
L 85
L 49
L 7
I
I
R 97
R 15
I
R 66
L 8
R 62
R 68
I
I
R 32
R 24
R 36
L 60
R 75
R 77
I
L 42
I
L 61
I
I
R 78
R 51
L 98
I
L 77
I
I...

output:

2556

result:

ok 1 number(s): "2556"

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 19528kb

input:

rtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtr
100
R 27
R 68
I
L 29
L 51
L 19
L 12
L 10
L 52
L 38
L 17
R 30
L 29
L 51
L 17
R 29
I
R 96
R 50
R 56
I
I
I
L 73
L 15
I
R 1
R 81
L 94
R 27
R 52
R 57
R 44
I
I
L 53
I
R 87
L 39
L 25
I
I
R 25
I
I
I
L 88
L ...

output:

67

result:

wrong answer 1st numbers differ - expected: '116', found: '67'