QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#280284 | #7780. Dark LaTeX vs. Light LaTeX | ucup-team1631# | TL | 564ms | 10780kb | C++23 | 6.5kb | 2023-12-09 14:55:04 | 2023-12-09 14:55:05 |
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;
}
template <typename Key, typename Val>
struct HashMap {
using u32 = uint32_t;
using u64 = uint64_t;
u32 cap, s;
vector<Key> keys;
vector<Val> vals;
vector<bool> flag;
u64 r;
u32 shift;
Val DefaultValue;
static u64 rng() {
u64 m = chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
m ^= m >> 16;
m ^= m << 32;
return m;
}
void reallocate() {
cap <<= 1;
vector<Key> k(cap);
vector<Val> v(cap);
vector<bool> f(cap);
u32 sh = shift - 1;
for (int i = 0; i < (int)flag.size(); i++) {
if (flag[i]) {
u32 hash = (u64(keys[i]) * r) >> sh;
while (f[hash]) hash = (hash + 1) & (cap - 1);
k[hash] = keys[i];
v[hash] = vals[i];
f[hash] = 1;
}
}
keys.swap(k);
vals.swap(v);
flag.swap(f);
--shift;
}
explicit HashMap()
: cap(8),
s(0),
keys(cap),
vals(cap),
flag(cap),
r(rng()),
shift(64 - __lg(cap)),
DefaultValue(Val()) {}
Val& operator[](const Key& i) {
u32 hash = (u64(i) * r) >> shift;
while (true) {
if (!flag[hash]) {
if (s + s / 4 >= cap) {
reallocate();
return (*this)[i];
}
keys[hash] = i;
flag[hash] = 1;
++s;
return vals[hash] = DefaultValue;
}
if (keys[hash] == i) return vals[hash];
hash = (hash + 1) & (cap - 1);
}
}
// exist -> return pointer of Val
// not exist -> return nullptr
const Val* find(const Key& i) const {
u32 hash = (u64(i) * r) >> shift;
while (true) {
if (!flag[hash]) return nullptr;
if (keys[hash] == i) return &(vals[hash]);
hash = (hash + 1) & (cap - 1);
}
}
// return vector< pair<const Key&, val& > >
vector<pair<Key, Val>> enumerate() const {
vector<pair<Key, Val>> ret;
for (u32 i = 0; i < cap; ++i)
if (flag[i]) ret.emplace_back(keys[i], vals[i]);
return ret;
}
int size() const { return s; }
// set default_value
void set_default(const Val& val) { DefaultValue = val; }
};
/**
* @brief Hash Map(可変長版)
* @docs docs/data-structure/hash-map.md
*/
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) {
vector<HashMap<int, ll>> cntT(T.size() + 1);
rep(l, 0, T.size()) rep(r, l + 1, T.size() + 1) {
++cntT[r - l][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) {
if (r - l > T.size()) continue;
ll res = ((l == 0 ? 0 : cnt[l - 1]) + eq) *
cntT[r - l][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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 564ms
memory: 5124kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 47ms
memory: 10752kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 60ms
memory: 10780kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: -100
Time Limit Exceeded
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...