QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466674 | #8512. Harmonic Operations | Swarthmore# | TL | 8ms | 19644kb | C++20 | 6.0kb | 2024-07-08 01:29:39 | 2024-07-08 01:29:41 |
Judging History
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;
cur = (N-cur)%N;
}
if (fl) {
revSums[cur]++;
negRevSums[(N-cur)%N]++;
} else {
sums[cur]++;
negSums[(N-cur)%N]++;
}
}
vl poly1 = multiply(negSums, sums);
//dbg(sums, negSums, revSums, negRevSums);
ll ans = 0;
F0R(i, sz(poly1)) {
if (ok[0][i%N]) ans += poly1[i];
}
//dbg(ans);
vl poly2 = multiply(revSums, sums);
F0R(i, sz(poly2)) {
if (ok[1][i%N]) ans += poly2[i] * 2;
}
//dbg(ans);
vl poly3 = multiply(revSums, negRevSums);
F0R(i, sz(poly3)) {
if (ok[0][i%N]) ans += poly3[i];
}
//dbg(ans);
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: 8ms
memory: 19416kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 19440kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 8ms
memory: 19480kb
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: 4ms
memory: 19420kb
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: 2ms
memory: 19480kb
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: 0
Accepted
time: 8ms
memory: 19644kb
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:
116
result:
ok 1 number(s): "116"
Test #7:
score: 0
Accepted
time: 2ms
memory: 19640kb
input:
tcldtcldtcldtcldtcldtcldtcldtcldtcld 100 L 20 I I I L 20 R 13 L 16 L 19 R 10 I I I L 11 R 30 R 30 I L 35 I L 28 R 23 R 24 L 20 R 15 I I L 13 I R 1 I R 6 I I L 22 I L 22 R 22 L 30 L 30 I I I R 35 I R 3 L 1 R 4 I R 11 R 2 R 21 R 15 I R 5 L 2 L 4 L 7 L 19 L 29 R 8 I L 24 I I I L 29 I R 35 R 32 I R 14 L...
output:
703
result:
ok 1 number(s): "703"
Test #8:
score: 0
Accepted
time: 8ms
memory: 19616kb
input:
wflbkhwflbkhwflbkhwflbkhwflbkhwflbkh 100 I R 28 R 13 R 7 R 29 I I I R 25 R 10 R 23 I R 26 I I L 18 I R 18 L 6 I I R 8 R 8 I R 6 L 16 I R 2 R 17 L 31 R 31 L 22 R 26 L 21 L 20 R 10 L 13 R 33 R 13 R 35 R 22 L 2 L 4 R 19 L 32 L 25 I L 31 R 10 R 17 R 15 L 6 L 9 R 31 R 20 I I R 4 I L 30 L 30 L 2 R 18 R 35...
output:
442
result:
ok 1 number(s): "442"
Test #9:
score: 0
Accepted
time: 8ms
memory: 19440kb
input:
mzgaokjwpmzgaokjwpmzgaokjwpmzgaokjwp 100 R 10 I L 24 L 8 I L 19 L 25 I I R 27 R 24 I I L 16 I I L 35 R 14 I L 23 R 17 R 16 R 4 R 4 L 29 I R 11 R 9 R 15 I L 18 I I L 25 R 13 L 24 I I L 8 I I I I L 24 I I L 19 L 23 I L 20 R 35 L 31 I I R 27 I I I L 35 R 16 L 10 R 28 R 14 I I R 30 R 18 L 16 L 6 L 12 R ...
output:
280
result:
ok 1 number(s): "280"
Test #10:
score: 0
Accepted
time: 2ms
memory: 19396kb
input:
gtvcymjngzntgtvcymjngzntgtvcymjngznt 100 L 33 L 5 R 31 R 18 I R 14 R 9 L 1 I R 1 R 15 L 15 I I I L 13 R 7 I I L 2 I L 3 I L 19 L 22 L 2 R 32 I L 1 R 24 R 23 I R 25 L 11 R 34 R 25 I L 25 R 22 R 34 I I L 2 R 13 L 3 I L 30 I R 7 R 20 I R 24 L 34 R 23 I L 26 R 22 I I I R 17 I I L 14 R 27 R 35 I L 34 L 3...
output:
206
result:
ok 1 number(s): "206"
Test #11:
score: 0
Accepted
time: 8ms
memory: 19504kb
input:
dvaauyemcqhrmduoumdvaauyemcqhrmduoum 100 L 21 R 12 R 30 L 13 I I L 1 L 31 R 4 L 20 I L 6 I L 29 R 19 L 12 R 25 R 25 I R 21 I L 12 L 25 R 35 L 8 R 7 R 29 I R 4 L 24 R 29 I I I L 12 L 24 R 19 L 33 L 4 I R 35 I R 16 I R 10 I R 18 R 7 L 33 I I R 22 L 16 L 7 L 20 R 32 I I R 27 I L 9 R 16 I I R 32 I R 1 L...
output:
180
result:
ok 1 number(s): "180"
Test #12:
score: 0
Accepted
time: 8ms
memory: 19428kb
input:
pkmsckbnjeeojagpdtfxlmlgofbrygcuqiahynrwooxgdruurdgxoowrnyhaiqucgyrbfoglmlxftdpgajoeejnbkcsmkplhxxhl 100 L 14 R 54 L 88 L 66 L 38 R 91 I I I I R 56 L 4 L 76 R 12 L 86 I I I I R 52 L 98 L 98 L 39 R 60 L 14 R 23 R 92 R 99 L 71 I I I I L 1 R 33 I R 65 L 72 I I I R 20 R 48 L 81 L 7 I R 72 R 14 I I R 10 ...
output:
75
result:
ok 1 number(s): "75"
Test #13:
score: 0
Accepted
time: 8ms
memory: 19644kb
input:
txgcggvgarkkflejgkaukutnsjogrglpdmocuhyiboientoffaaaffotneiobiyhucomdplgrgojsntukuakgjelfkkragvggcgxt 100 R 35 R 84 I R 68 R 24 L 42 L 24 R 16 R 80 R 95 L 9 L 26 L 96 R 64 I R 56 I L 5 R 83 R 2 R 57 R 28 I R 17 I R 11 I R 100 L 42 I L 89 I L 91 I I R 78 I R 30 L 6 I L 56 L 48 R 79 L 8 I R 5 L 25 R 2...
output:
76
result:
ok 1 number(s): "76"
Test #14:
score: 0
Accepted
time: 8ms
memory: 19472kb
input:
qhygenaiejhluibjfyjbdoslylsodbjyfjbiulhjeianegyhqydgoxbmbcuslmfqgraeqkpuerbnbreupkqeargqfmlsucbmbxogdy 100 L 41 R 73 R 41 I R 59 R 77 I I R 21 L 5 R 30 R 3 L 94 I L 36 R 2 R 85 L 39 L 17 R 47 I R 86 L 30 R 38 R 80 I R 39 I I L 99 I L 15 I L 76 L 68 L 91 I R 71 R 36 L 14 L 15 I L 63 R 71 I L 38 I R 3...
output:
48
result:
ok 1 number(s): "48"
Test #15:
score: -100
Time Limit Exceeded
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
20000100000