The Number of Good Subsets (LeetCode 1994)
Đề bài
1994. The Number of Good Subsets – Số lượng tập con tốt (LeetCode, độ khó Hard)
Cho một mảng số nguyên nums. Ta gọi một tập con của nums là tốt nếu tích các phần tử của nó có thể biểu diễn thành tích của một hoặc nhiều số nguyên tố phân biệt.
- Ví dụ, nếu
nums = [1, 2, 3, 4]:[2, 3],[1, 2, 3]và[1, 3]là các tập con tốt với tích lần lượt là6 = 2*3,6 = 2*3và3 = 3.[1, 4]và[4]không phải tập con tốt, với tích lần lượt là4 = 2*2và4 = 2*2.
Hãy trả về số lượng tập con tốt khác nhau của nums, lấy modulo $10^9 + 7$.
Một tập con của nums là một mảng bất kỳ thu được bằng cách xoá đi một số phần tử (có thể không xoá hoặc xoá hết) của nums. Hai tập con được coi là khác nhau khi và chỉ khi tập các chỉ số bị xoá của chúng khác nhau.
Ràng buộc:
- $1 \le$
nums.length$\le 10^5$ - $1 \le$
nums[i]$\le 30$
Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm numberOfGoodSubsets trong class Solution. Để chạy như một chương trình bình thường (và dùng khung chạy tay bên dưới), mình đặt thêm định dạng:
- Dữ liệu vào: dòng đầu là số nguyên $n$ (độ dài mảng), dòng thứ hai gồm $n$ số nguyên
nums[0], nums[1], ..., nums[n-1]. - Kết quả: một số nguyên là số tập con tốt, lấy modulo $10^9 + 7$.
Input: nums = [1,2,3,4]
Output: 64
1 2 3 4
---
6Input: nums = [4,2,3,15]
Output: 54
4 2 3 15
---
5Giải thích ví dụ của đề:
- Ví dụ 1: các tập con tốt là
[1,2]: tích bằng 2, là tích của số nguyên tố phân biệt 2.[1,2,3]: tích bằng 6, là tích của các số nguyên tố phân biệt 2 và 3.[1,3]: tích bằng 3, là tích của số nguyên tố phân biệt 3.[2]: tích bằng 2, là tích của số nguyên tố phân biệt 2.[2,3]: tích bằng 6, là tích của các số nguyên tố phân biệt 2 và 3.[3]: tích bằng 3, là tích của số nguyên tố phân biệt 3.
- Ví dụ 2: các tập con tốt là
[2]: tích bằng 2, là tích của số nguyên tố phân biệt 2.[2,3]: tích bằng 6, là tích của các số nguyên tố phân biệt 2 và 3.[2,15]: tích bằng 30, là tích của các số nguyên tố phân biệt 2, 3 và 5.[3]: tích bằng 3, là tích của số nguyên tố phân biệt 3.[15]: tích bằng 15, là tích của các số nguyên tố phân biệt 3 và 5.
1994. The Number of Good Subsets (LeetCode, Hard)
You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.
- For example, if
nums = [1, 2, 3, 4]:[2, 3],[1, 2, 3], and[1, 3]are good subsets with products6 = 2*3,6 = 2*3, and3 = 3respectively.[1, 4]and[4]are not good subsets with products4 = 2*2and4 = 2*2respectively.
Return the number of different good subsets in nums modulo $10^9 + 7$.
A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [1,2,3,4]
Output: 6
Explanation: The good subsets are:
- [1,2]: product is 2, which is the product of distinct prime 2.
- [1,2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [1,3]: product is 3, which is the product of distinct prime 3.
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [3]: product is 3, which is the product of distinct prime 3.Example 2:
Input: nums = [4,2,3,15]
Output: 5
Explanation: The good subsets are:
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5.
- [3]: product is 3, which is the product of distinct prime 3.
- [15]: product is 15, which is the product of distinct primes 3 and 5.Constraints:
- $1 \le$
nums.length$\le 10^5$ - $1 \le$
nums[i]$\le 30$
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.
Nói gọn lại, một tập con là tốt khi tích của nó lớn hơn 1 và không chia hết cho bình phương của số nguyên tố nào. Ở ví dụ 2 ([4,2,3,15]): số 4 = 2·2 nên tập nào có số 4 đều hỏng; còn [3,15] có tích 45 = 3·3·5 bị lặp số 3 nên cũng hỏng. Ngoài ra số 1 không làm thay đổi tích, nên thêm hay bớt số 1 vào một tập con tốt thì vẫn tốt – đó là lý do ví dụ 1 có cả [2] lẫn [1,2]. Riêng tập chỉ gồm toàn số 1 thì tích bằng 1, không phải tích của "một hoặc nhiều" số nguyên tố nên không tính.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Duyệt tất cả tập con – O(2^N · N)
Làm đúng theo đề: mỗi tập con ứng với một mask $n$ bit. Ta lần lượt nhân các phần tử được chọn vào biến product, và trước khi nhân số $x$ thì kiểm tra:
- $x$ không được chia hết cho bình phương của số nguyên tố nào (như 4, 8, 9, 12, 18, 25...);
- $x$ không được có thừa số nguyên tố chung với tích hiện tại, tức
gcd(product, x) == 1.
Cuối cùng tập con là tốt nếu qua được hết các kiểm tra và tích lớn hơn 1. Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// x không chia hết cho bình phương của số nguyên tố nào
bool squareFree(int x) {
for (int p = 2; p * p <= x; p++) {
if (x % (p * p) == 0) return false;
}
return true;
}
int numberOfGoodSubsets(vector<int>& nums) {
int n = (int) nums.size();
long long ans = 0;
for (int mask = 1; mask < (1 << n); mask++) {
long long product = 1;
bool ok = true;
for (int i = 0; i < n && ok; i++) {
if (mask >> i & 1) {
int x = nums[i];
// x phải không có thừa số lặp và không chung thừa số nào với tích hiện tại
if (!squareFree(x) || __gcd(product, (long long) x) > 1) ok = false;
else product *= x;
}
}
if (ok && product > 1) ans++;
}
return ans % 1000000007;
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
cout << sol.numberOfGoodSubsets(nums);
return 0;
}import sys
from math import gcd
from typing import List
class Solution:
# x không chia hết cho bình phương của số nguyên tố nào
def squareFree(self, x: int) -> bool:
p = 2
while p * p <= x:
if x % (p * p) == 0:
return False
p += 1
return True
def numberOfGoodSubsets(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for mask in range(1, 1 << n):
product = 1
ok = True
for i in range(n):
if mask >> i & 1:
x = nums[i]
# x phải không có thừa số lặp và không chung thừa số nào với tích hiện tại
if not self.squareFree(x) or gcd(product, x) > 1:
ok = False
break
product *= x
if ok and product > 1:
ans += 1
return ans % 1000000007
def main():
data = sys.stdin.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
print(Solution().numberOfGoodSubsets(nums))
if __name__ == "__main__":
main()Cách 2Quy hoạch động bitmask trên các số nguyên tố – O(N + 30 · 2^10)
Phương pháp xử lý: Quy hoạch động bitmask + tổ hợp. Cụ thể như sau.
Ta nhìn ra điều này: số trong dãy khá nhỏ ($1 \le$ nums[i] $\le 30$) nên nếu phân tích các số này ra thành tích các thừa số nguyên tố thì số lượng số nguyên tố chỉ $\le 10$, đó là các số $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}$.
Trước hết ta gọi $cnt[x]$ là số lượng số $x$ có trong dãy. Ví dụ dãy nums = [1, 2, 5, 2, 4, 1, 4] thì $cnt[1] = 2$, $cnt[2] = 2$, $cnt[4] = 2$, $cnt[5] = 1$. Vì giá trị chỉ từ 1 tới 30, thay vì xét từng phần tử ta xét từng giá trị $x$: trong một tập con tốt, mỗi giá trị $x \gt 1$ chỉ được lấy tối đa 1 lần (lấy 2 số $x$ thì thừa số của $x$ bị lặp), và nếu lấy thì có đúng $cnt[x]$ cách chọn xem lấy số $x$ ở vị trí nào.
Tiếp theo ta sàng lọc toàn bộ số mà khi phân tích ra có thừa số nguyên tố với lũy thừa $\gt 1$, ví dụ như mấy số 4, 8, 9, 12, 25... bỏ hết ra khỏi dãy, bởi vì mấy số này vô dụng (có mặt là tập con hỏng ngay). Sau đó gọi $listPrime[x]$ là tập hợp các thừa số nguyên tố khi phân tích $x$.
110: bit thứ 1 và bit thứ 2 bằng 1, tức là có sự xuất hiện của thừa số nguyên tố 3 và 5. Còn với số bị loại (như 4, 12) mình gán $listPrime = -1$.Rồi tới luôn 😄 nguyên liệu chuẩn bị đã xong xuôi, bây giờ ta quy hoạch động nào:
Với $f[i][mask]$ hiện tại, xét giá trị $x = i + 1$:
- Nếu bỏ qua giá trị $i + 1$: $f[i + 1][mask] \mathrel{+}= f[i][mask]$.
- Nếu nhận giá trị $i + 1$ thì phải kiểm tra: khi kết nạp nó vào, đã có thừa số nguyên tố nào nằm sẵn trong $mask$ mà $i + 1$ cũng có hay chưa? Tức là kiểm tra
mask & listPrime[i + 1] == 0hay không. Nếu đúng thì: $f[i + 1][mask \mid listPrime[i + 1]] \mathrel{+}= f[i][mask] \cdot cnt[i + 1]$. Ta nhân với $cnt[i + 1]$ là bởi vì số lượng số $i + 1$ là $cnt[i + 1]$, nên sẽ có $cnt[i + 1]$ cách chọn.
Đáp án là tổng các $f[30][mask]$ với $mask$ từ $1$ tới $2^{10} - 1$ ($mask = 0$ là chưa chọn số nguyên tố nào, tích bằng 1, không tính).
$\text{ans} = 2^{cnt[1]} \cdot \sum_{mask = 1}^{2^{10} - 1} f[30][mask]$.
Minh hoạ quy hoạch động theo từng giá trị
Em nhập mảng nums (tối đa 15 số, mỗi số từ 1 tới 30) rồi bấm Tiếp. Mỗi ô là một trạng thái khác 0: phía trên ghi tập số nguyên tố trong $mask$, phía dưới là $f[mask]$. Mình chỉ dừng ở những giá trị $x$ có trong mảng (giá trị không có thì $cnt[x] = 0$, hàng $f$ giữ nguyên):
Source code để các bạn tham khảo nếu làm theo hướng này (hàm getMask chính là bước tính $listPrime[x]$, trả về $-1$ với số có thừa số lặp):
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
long long f[31][1 << 10];
// dãy bit các thừa số nguyên tố của x, trả về -1 nếu x có thừa số mũ >= 2
int getMask(int x) {
int res = 0;
for (int p = 0; p < 10; p++) {
int c = 0;
while (x % primes[p] == 0) {
x /= primes[p];
c++;
}
if (c >= 2) return -1;
if (c == 1) res |= (1 << p);
}
return res;
}
class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
long long cnt[31] = {0};
int listPrime[31];
for (int x : nums) cnt[x]++;
for (int x = 1; x <= 30; x++) listPrime[x] = getMask(x);
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 0; i < 30; i++) {
int x = i + 1;
for (int mask = 0; mask < (1 << 10); mask++) {
if (f[i][mask] == 0) continue;
(f[i + 1][mask] += f[i][mask]) %= MOD;
if (x > 1 && listPrime[x] != -1 && (mask & listPrime[x]) == 0) {
int nmask = mask | listPrime[x];
(f[i + 1][nmask] += f[i][mask] * cnt[x]) %= MOD;
}
}
}
long long ans = 0;
for (int mask = 1; mask < (1 << 10); mask++) {
(ans += f[30][mask]) %= MOD;
}
for (int k = 0; k < cnt[1]; k++) {
(ans *= 2) %= MOD;
}
return (int) ans;
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
cout << sol.numberOfGoodSubsets(nums);
return 0;
}import sys
from typing import List
MOD = 1000000007
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# dãy bit các thừa số nguyên tố của x, trả về -1 nếu x có thừa số mũ >= 2
def getMask(x: int) -> int:
res = 0
for p in range(10):
c = 0
while x % primes[p] == 0:
x //= primes[p]
c += 1
if c >= 2:
return -1
if c == 1:
res |= 1 << p
return res
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
cnt = [0] * 31
for x in nums:
cnt[x] += 1
listPrime = [0] + [getMask(x) for x in range(1, 31)]
f = [[0] * (1 << 10) for _ in range(31)]
f[0][0] = 1
for i in range(30):
x = i + 1
for mask in range(1 << 10):
if f[i][mask] == 0:
continue
f[i + 1][mask] = (f[i + 1][mask] + f[i][mask]) % MOD
if x > 1 and listPrime[x] != -1 and (mask & listPrime[x]) == 0:
nmask = mask | listPrime[x]
f[i + 1][nmask] = (f[i + 1][nmask] + f[i][mask] * cnt[x]) % MOD
ans = sum(f[30][1:]) % MOD
ans = ans * pow(2, cnt[1], MOD) % MOD
return ans
def main():
data = sys.stdin.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
print(Solution().numberOfGoodSubsets(nums))
if __name__ == "__main__":
main()Khung chạy tay bên dưới chạy theo code C++ ở trên. Vì vòng mask chạy tới $2^{10} = 1024$ lần mà đa số $f$ bằng 0 (bị continue), mình gom những lần đó lại, chỉ dừng ở các mask có $f \ne 0$; với các giá trị $x$ không có trong mảng hoặc bị loại thì gom cả vòng mask thành 1 bước "chép nguyên hàng". Trạng thái mask được ghi dưới dạng tập số nguyên tố cho dễ đọc:
Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng $f$ có $31 \times 2^{10}$ ô, cỡ 31 nghìn ô, coi như hằng số: $O(30 \cdot 2^{10})$.
- Thời gian: đếm $cnt$ mất $O(N)$, quy hoạch động mất $30 \times 1024 \approx 3 \cdot 10^4$ phép, nên tổng cộng $O(N + 30 \cdot 2^{10})$ – rất nhanh.
long long rồi mới lấy modulo.Cách 3Code AC của mình: QHĐ theo từng phần tử + tổ hợp cho 17, 19, 23, 29 – O(N · 2^6)
Code dưới đây của mình đã AC trên LeetCode. Ý tưởng vẫn là quy hoạch động bitmask như cách 2, nhưng có hai điểm khác:
- Quy hoạch động theo từng phần tử của mảng ($dp[i][mask]$: đã xét $i$ phần tử đầu), nên không cần nhân với $cnt$: mỗi phần tử tự có 2 lựa chọn lấy / không lấy. Số 1 có $listPrime = 0$ nên "lấy" luôn hợp lệ, tự động nhân đôi số cách – đúng bằng việc nhân $2^{cnt[1]}$.
- Mask chỉ còn 6 bit cho các số nguyên tố $2, 3, 5, 7, 11, 13$. Các số nguyên tố lớn $17, 19, 23, 29$ có nhận xét đặc biệt: trong phạm vi tới 30, số duy nhất chia hết cho chúng là chính chúng (vì $17 \cdot 2 = 34 \gt 30$). Nên với mỗi số nguyên tố lớn $q$, ta chỉ có $cnt[q] + 1$ lựa chọn: không lấy, hoặc lấy đúng 1 trong $cnt[q]$ số $q$. Các lựa chọn này độc lập với phần còn lại, đếm bằng tổ hợp (quy tắc nhân).
- Tập con có ít nhất một số nguyên tố nhỏ: $S \cdot Q$ (phần số nguyên tố lớn chọn tự do).
- Tập con không có số nguyên tố nhỏ nào: phần số nguyên tố lớn phải chọn ít nhất 1 số, có $Q - 1$ cách, nhân với $2^{cnt[1]}$ cách chọn các số 1.
POW.Source code để các bạn tham khảo nếu làm theo hướng này (bản Python mình dùng mảng lăn 64 phần tử thay cho bảng $dp$ to, cùng logic):
#include <bits/stdc++.h>
using namespace std;
int prime[6] = {2, 3, 5, 7, 11, 13};
int otherPrime[4] = {17, 19, 23, 29};
int listPrime[100005];
int cnt[35];
const long long MOD = 1000000007;
long long dp[100005][(1 << 6) + 2];
long long POW(long long x, long long n) {
if (n == 0) {
return 1LL;
}
long long tmp = POW(x, n >> 1);
(tmp *= tmp) %= MOD;
if (n % 2 == 1) {
(tmp *= x) %= MOD;
}
return tmp;
}
class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
memset(dp, 0, sizeof(dp));
memset(listPrime, 0, sizeof(listPrime));
memset(cnt, 0, sizeof(cnt));
int n = (int) nums.size();
for (int i = 1; i <= n; i++) {
int value = nums[i - 1];
if (value == 1) {
cnt[1]++;
continue;
}
bool found = false;
for (int p = 0; p < 4; p++) {
if (value == otherPrime[p]) {
listPrime[i] = -1;
cnt[value]++;
found = true;
break;
}
}
if (found == true) {
continue;
}
for (int p = 0; p < 6; p++) {
int cntValue = 0;
while ((value % prime[p]) == 0) {
cntValue++;
value /= prime[p];
}
if (cntValue >= 2) {
listPrime[i] = -1;
break;
}
if (cntValue == 1) {
listPrime[i] |= (1 << p);
}
}
}
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << 6); mask++) {
if (dp[i][mask] == 0) {
continue;
}
(dp[i + 1][mask] += dp[i][mask]) %= MOD;
if (listPrime[i + 1] != -1 && (mask & listPrime[i + 1]) == 0) {
(dp[i + 1][mask | listPrime[i + 1]] += dp[i][mask]) %= MOD;
}
}
}
long long ans = 0;
for (int mask = 1; mask < (1 << 6); mask++) {
(ans += dp[n][mask]) %= MOD;
}
(ans *= (long long) (cnt[17] + 1)) %= MOD;
(ans *= (long long) (cnt[19] + 1)) %= MOD;
(ans *= (long long) (cnt[23] + 1)) %= MOD;
(ans *= (long long) (cnt[29] + 1)) %= MOD;
long long other = 1;
(other *= (long long) (cnt[17] + 1)) %= MOD;
(other *= (long long) (cnt[19] + 1)) %= MOD;
(other *= (long long) (cnt[23] + 1)) %= MOD;
(other *= (long long) (cnt[29] + 1)) %= MOD;
other--;
(other *= POW(2LL, cnt[1])) %= MOD;
return (int) ((ans + other) % MOD);
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
cout << sol.numberOfGoodSubsets(nums);
return 0;
}import sys
from typing import List
MOD = 1000000007
prime = [2, 3, 5, 7, 11, 13]
otherPrime = [17, 19, 23, 29]
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
n = len(nums)
listPrime = [0] * (n + 1)
cnt = [0] * 35
for i in range(1, n + 1):
value = nums[i - 1]
if value == 1:
cnt[1] += 1
continue
if value in otherPrime:
listPrime[i] = -1
cnt[value] += 1
continue
for p in range(6):
cntValue = 0
while value % prime[p] == 0:
cntValue += 1
value //= prime[p]
if cntValue >= 2:
listPrime[i] = -1
break
if cntValue == 1:
listPrime[i] |= 1 << p
# dp lăn: chỉ giữ hàng dp[i] hiện tại (64 trạng thái) cho đỡ tốn bộ nhớ
dp = [0] * (1 << 6)
dp[0] = 1
for i in range(n):
lp = listPrime[i + 1]
ndp = dp[:] # không chọn nums[i]
if lp != -1:
for mask in range(1 << 6):
if dp[mask] and (mask & lp) == 0:
ndp[mask | lp] = (ndp[mask | lp] + dp[mask]) % MOD
dp = ndp
ans = sum(dp[1:]) % MOD
for q in otherPrime:
ans = ans * (cnt[q] + 1) % MOD
other = 1
for q in otherPrime:
other = other * (cnt[q] + 1) % MOD
other -= 1
other = other * pow(2, cnt[1], MOD) % MOD
return (ans + other) % MOD
def main():
data = sys.stdin.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
print(Solution().numberOfGoodSubsets(nums))
if __name__ == "__main__":
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng
dp[100005][66]kiểulong long, khoảng 53 MB, tức $O(N \cdot 2^6)$. Vì mỗi hàng chỉ phụ thuộc hàng trước nên có thể dùng mảng lăn để còn $O(2^6)$ như bản Python. - Thời gian: $n$ phần tử, mỗi phần tử duyệt 64 mask: $O(N \cdot 2^6)$, khoảng $6.4 \cdot 10^6$ phép với $n = 10^5$.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét