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\to mask=0000011100\to 4+8+16=28$.
• Số $12\to mask=0000001100\to 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

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

2. Cặp khác mask

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

$\to$ 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: $𝒪(n)$.
• Duyệt tất cả cặp $mask(i,j)$ với $0\le i<j<1024$: $𝒪({1024}^2)$ (hằng số chấp nhận được).

$\to$ Độ phức tạp: $𝒪(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';
    }
}