Bước 1: Biểu diễn số đã cho bằng bitmask

• Mỗi số $x$ sẽ được biểu diễn bằng một bitmask $10$-bit (tương ứng với các chữ số $0$ đến $9$).

Ví dụ:

• Số $123 \rightarrow mask = 0000011100 \rightarrow 4 + 8 + 16 = 28$.
• Số $12 \rightarrow mask = 0000001100 \rightarrow 4 + 8 = 12$.

Lưu ý: Có tối đa $2^{10} = 1024$ bitmask khác nhau.

Bước 2: Đếm số lượng mỗi bitmask

• Ta tạo mảng $cnt[1024]$, với $cnt[x]$ là số lượng số có $mask = x$.

Bước 3: Đếm số cặp hợp lệ

Có hai loại cặp:

1. Cặp có cùng mask

$\rightarrow$ Chọn $2$ trong số $cnt[m]$ số: $\dfrac{cnt[m] \times (cnt[m] - 1)}{2}$.

2. Cặp khác mask

• Nếu mask1 & mask1 != 0 thì có chữ số trùng.

$\rightarrow$ Với $i < j$, cộng $cnt[i] \times cnt[j]$ nếu i & j != 0.

Độ phức tạp

• Duyệt $n$ số để tính mask: $\mathcal{O}(n)$.
• Duyệt tất cả cặp $mask(i, j)$ với $0 \leq i < j < 1024$: $\mathcal{O}(1024^{2})$ (hằng số chấp nhận được).

$\rightarrow$ Độ phức tạp: $\mathcal{O}(n + 1024^{2})$.

Code tham khảo

int get_mask(long long x) {
    int mask = 0;
    while (x) {
        mask |= 1 << (x % 10);
        x /= 10;
    }
    return mask;
}

void solve() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> cnt(1024, 0);
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            long long x; cin >> x;
            int a = get_mask(x);
            cnt[a]++;
        }
        for (int i = 0; i < 1024; i++) {
            res += cnt[i] * (cnt[i] - 1) / 2;
            for (int j = i + 1; j < 1024; j++) 
                if (i & j) res += cnt[i] * cnt[j];
        }
        cout << res << '\n';
    }
}