Cho mảng nums và số k. XOR của segment [left, right] là XOR các phần tử từ left đến right. Cần tìm số phần tử tối thiểu phải thay đổi để XOR của mọi segment kích thước k đều bằng 0.
Ví dụ: nums = [3,4,5,2,1,7,3,4,7], k = 3 → output = 3 (sửa indices 2,3,4 thành [3,4,7,3,4,7,3,4,7]).
Giải thuật (DP trên nhóm modulo k)
- Chia mảng thành k nhóm theo index % k. Mỗi nhóm phải có cùng giá trị sau sửa đổi (để XOR k phần tử liên tiếp = 0).
- DP[xor_value] = max số phần tử giữ nguyên đạt được XOR prefix = xor_value.
- Xử lý từng nhóm: new_dp[xor] = max(prev + cnt) với cnt = tần suất giá trị trong nhóm.
- Kết quả = n - dp[0].
Code Python
def solve(nums, k):
LIMIT = 2**10 # 1024
temp = [[0] * LIMIT for _ in range(k)]
for i, x in enumerate(nums):
temp[i % k][x] += 1
dp = [-2000] * LIMIT
dp[0] = 0
for row in temp:
maxprev = max(dp)
new_dp = [maxprev] * LIMIT
for i, cnt in enumerate(row):
if cnt > 0:
for j, prev in enumerate(dp):
new_dp[i ^ j] = max(new_dp[i ^ j], prev + cnt)
dp = new_dp
return len(nums) - dp[0]
nums = [3, 4, 5, 2, 1, 7, 3, 4, 7]
k = 3
print(solve(nums, k)) # 3
Đầu vào / Đầu ra
Input: [3,4,5,2,1,7,3,4,7], 3
Output: 3