Đếm số mảng con có thể sắp xếp thành palindrome trong C++

Cho mảng số nguyên. Nhiệm vụ: đếm số mảng con (subarray) mà các phần tử có thể sắp xếp lại thành palindrome. Palindrome là dãy đối xứng qua trung tâm.

Ví dụ

Đầu vào − arr[] = {3, 3, 1, 4, 2, 1, 5}

Đầu ra − 9

Giải thích − Các mảng con hợp lệ: {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1,2,1}, {1,3,1} (đếm trùng lặp nếu vị trí khác nhau).

Đầu vào − arr[] = {2, 5, 5, 2, 1}

Đầu ra − 8

Giải thích − {2}, {5}, {5}, {2}, {1}, {5,2,5}, {2,5,2}, {2,5,5,2}.

Phương pháp giải

Một dãy có thể sắp thành palindrome khi số phần tử xuất hiện lẻ lần ≤ 1. Dùng bitmask: mỗi bit đại diện cho tính chẵn/lẻ của tần suất một giá trị. Duyệt mọi mảng con [i..j], cập nhật bitmask bằng XOR. Kiểm tra bitmask có tối đa 1 bit 1 bằng !(mask & (mask-1)).

• Hàm check(long long mask) trả về true nếu mask là 0 hoặc lũy thừa của 2.
• Hàm palindromes_rearrange(int arr[], int size):
  • Khởi tạo count = 0.
  • Với mỗi i từ 0 đến size-1:
    • mask = 0.
    • Với j từ i đến size-1:
      • mask ^= (1LL << arr[j]).
      • Nếu mask == 0 || check(mask) → count++.
  • Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

bool check(long long mask) {
    return !(mask & (mask - 1LL));
}

int palindromes_rearrange(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        long long mask = 0LL;
        for (int j = i; j < size; j++) {
            long long val = 1LL << arr[j];
            mask ^= val;
            if (mask == 0LL || check(mask)) count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 3, 1, 4, 2, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of sub-arrays whose elements can be re-arranged to form palindromes are: " << palindromes_rearrange(arr, size);
    return 0;
}

Đầu ra

Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9