Hướng dẫn giải của [ClueOJ x QTOJ] Thi thử TS10 2025 - Dãy mèo ma thuật
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1: ~n \le 10~, ~a_i \le 50~.
Với mỗi đoạn con, ta nhân tất cả các phần tử với nhau và kiểm tra xem số đó có phải số chính phương không.
Độ phức tạp: ~O~ (~n^2~).
Subtask 2: ~n \le 1000~, ~a_i \le 1000~.
Với mỗi số, ta sẽ phân tích chúng ra thừa số nguyên tố. Ta có thể duyệt từng số nguyên tố và phân tích.
Gọi ~cnt_i~ là số mũ của thừa số nguyên tố ~i~. Đoạn con ta đang xét sẽ có dạng ~\prod_{i=1}^{1000} i^{cnt_i}~.
Dễ thấy, một đoạn con thỏa mãn sẽ có mọi ~cnt_i~ là chẵn.
Để tăng tốc thuật toán, ta cần tiền xử lý một vector <int> divi[i] chứa các thừa số nguyên tố của ~a_i~.
Độ phức tạp: ~O~ (~n^2 \times log_2 {a_i}~).
Subtask 3: ~a_i~ là các số nguyên tố.
Với subtask này, kết quả chỉ đơn giản là đoạn con dài nhất mà số lần xuất hiện của từng phần tử đều chẵn.
Có nhiều cách thực hiện điều này. Một trong số các cách đó là sử dụng XOR Hashing.
Ta sẽ sinh ra ~10^6 + 3~ giá trị ~hash_i~ ngẫu nhiên, ~1 \le hash_i \le 10^{18}~.
Tuy rằng số 64 bit là đủ, nhưng trong code sinh test, mình đã sử dụng số 256 bit.
Dễ thấy: Nếu một đoạn con có số lần xuất hiện của từng phần tử đều là chẵn, thì khi ta ~XOR~ các giá trị ~hash~ lại, kết quả sẽ là ~0~.
Vì vậy: Gán ~a_i = hash_{a_i}~, bài toán trở về: Tìm đoạn con dài nhất thỏa mãn ~XOR~ của cả đoạn con là ~0~.
Điều này có thể thực hiện bằng tổng tiền tố.
Độ phức tạp: ~O~ (~n~).
Subtask 4: ~a_i~ là các lũy thừa của 2.
Ta gán ~a_i = log2 (a_i)~. Dễ thấy: Tích một đoạn con, có các phần tử là lũy thừa của 2, là số chính phương khi và chỉ khi tổng các số mũ là chẵn.
Vì vậy, bài toán trở về: Tìm đoạn con dài nhất thỏa mãn tổng các phần tử là chẵn.
Điều này có thể thực hiện bằng tổng tiền tố.
Độ phức tạp: ~O~ (~n~).
Subtask 5: Không có ràng buộc gì thêm.
Mở rộng subtask 3, ta thấy: Ta sẽ cần ~XOR~ mọi thừa số nguyên tố của ~a_i~ thay vì chính nó.
Ta sử dụng sàng nguyên tố để phân tích một số ra thừa số nguyên tố.
Độ phức tạp: ~O~ (~n \times log_2 a_i~).
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long maxn = 1e6 + 5;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
int spf[maxn + 1], a[maxn + 1], Huy, Dung, n;
unsigned long long prime_hash[maxn + 1], h[maxn + 1];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace subtask3
{
void sieve(void)
{
for (int i = 1; i <= maxn; ++i)
spf[i] = i;
for (int i = 2; i <= maxn; ++i)
if (spf[i] == i)
{
prime_hash[i] = rng();
if (1LL * i * i <= maxn)
{
for (int j = i * i; j <= maxn; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
vector <int> phan_tich(int x)
{
vector <int> res;
while (x > 1)
{
int p = spf[x];
int cnt = 0;
while (x % p == 0)
{
x /= p;
cnt++;
}
if (cnt % 2 == 1)
res.push_back(p);
}
return res;
}
unordered_map <unsigned long long, int> seen;
int d[maxn + 5];
void solution(void)
{
sieve();
seen[0] = 0;
unsigned long long H = 0ULL;
d[1] = 1;
for (int i = 2; i <= maxn; i++){
if (d[i / spf[i]] % spf[i] == 0) d[i] = d[i / spf[i]] / spf[i];
else d[i] = d[i / spf[i]] * spf[i];
}
//for (int i = 1; i <= n; i++) a[i] = d[a[i]];
for (int i = 1; i <= n; ++i)
{
vector <int> primes = phan_tich(a[i]);
for (int p : primes)
H ^= prime_hash[p];
if (seen.count(H))
{
Dung = max(Dung, i - seen[H]);
}
else
seen[H] = i;
}
cout << Dung;
}
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string Tasks = "meow";
if (fopen((Tasks + ".inp").c_str(), "r"))
{
freopen((Tasks + ".inp").c_str(), "r", stdin);
freopen((Tasks + ".out").c_str(), "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
subtask3 :: solution();
return 0;
}
Bình luận