Bạn sử dụng markdown để viết nhé!
# Lời giải tham khảo
Chuyển xâu S về dạng số nguyên 32bit. Kí tự xuất hiện S tương ứng với bật bit thứ i.\
['a'..'z'] = [0 .. 25].\
**Ví dụ:** S = "the" ➙ 2^19 + 2^7 + 2^4 = 524432.\
Duyệt qua **2^n - 1** trạng thái. Đếm xem có bao nhiêu trạng thái **or** bằng **2^26 - 1** \
Với mỗi trạng thái **mask** đã duyệt ta lưu vào **f[mask]**.\
Từ đó ta có thể lấy luôn trạng thái đã duyệt mà không cần phải duyệt lại từ đầu, **bỏ được 1 for O(n)** \
**Công thức truy hồi: f[mask] = a[id] | f[mask - (1 << id)]** \
• **id:** bit bật quan trọng nhất của mask
**CODE: O(2^n)**
```
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
const int limit = (1 << 26) - 1;
int n;
int a[25];
int f[limit];
string s;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
FOR(i,0,n-1)
{
cin >> s;
for (char c:s) a[i] |= (1 << (c - 'a'));
}
int res = 0;
FOR(mask,1,(1 << n) - 1)
{
int id = __builtin_ffs(mask) - 1; // Vi tri bit 1 quan trong nhat cua mask
f[mask] = (a[id] | f[mask - (1 << id)]);
res += (f[mask] == limit);
}
return cout << res, 0;
}
```
hungkm466
Created at
1 likes