Tóm tắt đề bài

Cho một xâu \(S\) và \(N\) xâu \(T[i]\). Với mỗi \(T[i]\), ta nói \(T[i]\) dùng được nếu ta có thể chọn “một vài ký tự” trong \(T[i]\) sao cho các ký tự được chọn đều xuất hiện trong \(S\) (hiểu tối thiểu là chọn ít nhất 1 ký tự thỏa điều kiện).

Hỏi có bao nhiêu cách chọn một tập con không rỗng các xâu \(T[i]\) sao cho mỗi xâu được chọn đều “dùng được”. Nếu không có cách nào thì in ra \(-1\).

Phân tích

• Vì chỉ cần “chọn một vài ký tự” từ \(T[i]\) mà các ký tự đó xuất hiện trong \(S\), nên:
  • \(T[i]\) dùng được khi và chỉ khi \(T[i]\) có ít nhất một ký tự thuộc tập ký tự của \(S\).
• Khi đã biết có \(k\) xâu dùng được, số cách chọn tập con không rỗng từ \(k\) phần tử là:

• Ràng buộc: \(N \le 10\), \(|S|, |T[i]| \le 100\), nên có thể kiểm tra từng xâu trực tiếp.
• Code AC dùng bitmask để biểu diễn tập ký tự (nhưng lưu ý code đang ánh xạ hơi “lạ”: chỉ xét các ký tự a,b,c,y,z,.,, và bỏ qua ký tự khác; trong đề chuẩn chỉ có a..z, cách đúng là map đủ 26 chữ).

Hướng giải quyết

Nhận xét

• Ta chỉ quan tâm tập ký tự xuất hiện trong \(S\) và trong từng \(T[i]\), không quan tâm số lần xuất hiện.
• Điều kiện \(T[i]\) dùng được tương đương:

Thuật toán

1. Tạo bitmask \(mask_S\) biểu diễn các ký tự xuất hiện trong \(S\).
   • Với bài chuẩn a..z, dùng 26 bit: ký tự ch có bit \((ch - 'a')\).
2. Với mỗi \(T[i]\):
   • Tạo bitmask \(mask_i\).
   • Nếu \((mask_i \& mask_S) \neq 0\) thì \(T[i]\) dùng được, tăng biến đếm \(k\).
3. Kết luận:
   • Nếu \(k = 0\) in \(-1\) (theo đề).
   • Ngược lại in \(2^k - 1\).

Lỗi dễ gặp / lưu ý

• Phải hiểu “một vài ký tự” là ít nhất một ký tự, nên cần giao không rỗng.
• Output theo đề là \(-1\) nếu không có cách; trong code AC lại in 0. Khi làm theo đề, cần in \(-1\).
• Nếu \(k\) có thể lớn, cần lũy thừa modulo; nhưng ở đây \(N \le 10\) nên dùng \(2^k\) trực tiếp an toàn.

Độ phức tạp

• Thời gian: \(O(|S| + \sum |T[i]|)\), tối đa khoảng \(O(1100)\).
• Bộ nhớ: \(O(1)\) (ngoài lưu input).

Code tham khảo

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

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

    string S;
    int N;
    cin >> S >> N;
    vector<string> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];

    // Bitmask 26-bit cho 'a'..'z'
    int maskS = 0;
    for (char c : S) maskS |= 1 << (c - 'a');

    int k = 0; // số xâu T[i] dùng được
    for (auto &s : T) {
        int mask = 0;
        for (char c : s) mask |= 1 << (c - 'a');
        if ((mask & maskS) != 0) k++;
    }

    if (k == 0) {
        cout << -1 << "\n";
    } else {
        cout << ((1LL << k) - 1) << "\n";
    }
    return 0;
}