QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#280122 | #7780. Dark LaTeX vs. Light LaTeX | ucup-team1631# | TL | 1ms | 3924kb | C++23 | 3.8kb | 2023-12-09 14:00:26 | 2023-12-09 14:00:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
return a > b ? (a = b, 1) : 0;
}
class RollingHash {
public:
static long long generate_base() {
std::random_device rd;
std::mt19937_64 rng(rd());
std::uniform_int_distribution<long long> rand(1, mod - 1);
return rand(rng);
}
RollingHash() = default;
RollingHash(const std::string& s, long long base)
: RollingHash(std::vector<char>(s.begin(), s.end()), base) {}
template <typename T>
RollingHash(const std::vector<T>& s, long long base)
: base(base), hashed(s.size() + 1), power(s.size() + 1) {
power[0] = 1;
for (int i = 0; i < (int)s.size(); ++i) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
}
long long query(int l, int r) const {
return add(hashed[r], mod - mul(hashed[l], power[r - l]));
}
long long combine(long long h1, long long h2, int len2) const {
return add(mul(h1, power[len2]), h2);
}
void push_back(char c) {
power.push_back(mul(power.back(), base));
hashed.push_back(add(mul(hashed.back(), base), c));
}
private:
static constexpr long long mod = (1LL << 61) - 1;
static inline long long add(long long a, long long b) {
if ((a += b) >= mod) a -= mod;
return a;
}
static inline long long mul(long long a, long long b) {
__int128_t c = (__int128_t)a * b;
return add(c >> 61, c & mod);
}
const long long base;
std::vector<long long> hashed, power;
};
std::vector<int> z_array(const std::string& s) {
int n = s.size();
std::vector<int> z(n);
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
int k = i - l;
if (i <= r && z[k] < r - i + 1) {
z[i] = z[k];
} else {
l = i;
if (i > r) r = i;
while (r < n && s[r - l] == s[r]) ++r;
--r;
z[i] = r - l + 1;
}
}
return z;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
for (int i = 0; i < (int)v.size(); ++i) {
os << v[i];
if (i < (int)v.size() - 1) os << " ";
}
return os;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
string S, T;
cin >> S >> T;
const ll base = RollingHash::generate_base();
RollingHash rhs(S, base), rht(T, base);
auto calc = [&](string& S, string& T, auto& rhs, auto& rht,
bool eq = true) {
map<int, ll> cntT;
rep(l, 0, T.size()) rep(r, l + 1, T.size() + 1) {
++cntT[rht.query(l, r)];
}
int N = S.size();
ll ans = 0;
rep(r, 1, N + 1) {
auto U = S.substr(r) + "$" + S.substr(0, r);
auto z = z_array(U);
vector<int> cnt(r + 1);
rep(i, 0, r) {
++cnt[i];
--cnt[i + z[N - r + 1 + i]];
}
rep(i, 0, r) cnt[i + 1] += cnt[i];
rep(l, 0, r) {
ll res =
((l == 0 ? 0 : cnt[l - 1]) + eq) * cntT[rhs.query(l, r)];
ans += res;
}
}
return ans;
};
ll ans = calc(S, T, rhs, rht, true) + calc(T, S, rht, rhs, false);
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: -100
Time Limit Exceeded
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...