Editorial for Đoạn quà may mắn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Chỉ cần xét số mũ của các thừa số nguyên tố

Tích là số chính phương khi và chỉ khi số mũ của từng số nguyên tố trong tích đều chẵn. Với mỗi a_i, hãy chỉ giữ lại thông tin số mũ lẻ.

Gợi ý 2 - Dùng mặt nạ và XOR tiền tố

Vì a_i <= 30, chỉ có 10 số nguyên tố có thể xuất hiện. Biểu diễn số mũ lẻ bằng một bitmask. Đoạn [l,r] có tích chính phương khi XOR các mask trên đoạn bằng 0, hay hai XOR tiền tố tại l-1 và r bằng nhau.

Lời giải đầy đủ

Mặt nạ của một số

Với mỗi giá trị từ 1 đến 30, phân tích nó ra thừa số nguyên tố. Bit của một nguyên tố được bật nếu số mũ của nguyên tố đó là lẻ. Mặt nạ này chính là thông tin cần thiết để biết tích có phải số chính phương hay không.

Khi nhân các số, tính chẵn lẻ của số mũ được cộng theo modulo 2, tức là XOR các mặt nạ. Một tích là số chính phương đúng khi mặt nạ kết quả bằng 0.

Đếm đoạn

Gọi pref_i là XOR mặt nạ của i hộp đầu. Đoạn [l,r] may mắn khi:

pref_r XOR pref_(l-1) = 0.

Điều này tương đương pref_r = pref_(l-1). Vì thế, khi quét từ trái sang phải, với mỗi mặt nạ tiền tố hiện tại, cộng vào đáp án số lần mặt nạ đó đã xuất hiện. Khởi tạo tần suất mặt nạ 0 bằng 1 để tính các đoạn bắt đầu từ hộp đầu tiên.

Độ phức tạp

Có 10 số nguyên tố không vượt quá 30.

  • Thời gian: O(10N).
  • Bộ nhớ: O(1).
Code C++17
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int squareFreeMask[31] = {};

    for (int value = 1; value <= 30; ++value) {
        int remaining = value;
        int mask = 0;
        for (int bit = 0; bit < 10; ++bit) {
            int parity = 0;
            while (remaining % primes[bit] == 0) {
                remaining /= primes[bit];
                parity ^= 1;
            }
            if (parity) mask |= (1 << bit);
        }
        squareFreeMask[value] = mask;
    }

    int n;
    cin >> n;

    long long frequency[1 << 10] = {};
    frequency[0] = 1;

    int prefixMask = 0;
    long long answer = 0;
    for (int i = 0; i < n; ++i) {
        int value;
        cin >> value;
        prefixMask ^= squareFreeMask[value];
        answer += frequency[prefixMask];
        ++frequency[prefixMask];
    }

    cout << answer << '\n';
    return 0;
}

Loading...