Editorial for Bedao Regular Contest 02 - PXOR


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét: để ý rằng từ ~1~ đến ~5000~ thì số nguyên tố lớn nhất có thể tạo ra mà bằng tổng XOR của các số khác chỉ có thể là ~8191~. Tránh bị TLE thì ta sẽ sàng nguyên tố để tìm các số nguyên tố từ ~1~ đến ~8192~, như vậy là ta có thể đoán độ phức tạp là: ~O(T \times 1000 \times 8191)~

Xử lý các kết quả bị trùng lặp thì ta sẽ:

Gọi ~v~ là mảng lưu các phần tử khác nhau trong ~a~

Gọi ~c~ là mảng để đếm số lần xuất hiện của các phần tử trong ~a~

Gọi ~f[i][j]~ là số lượng tập con có thể tạo ra với ~i~ phần tử sao cho tổng XOR của ~i~ phần tử này bằng ~j~

Cơ sở: ~f[0][0] = 1~

Nhận xét: để ý thêm rằng ~f[0][j]~ sẽ phải bằng tổng của các ~f[1][j]~ và ngược lại ( áp dụng rolling array ), vì thế ta sẽ có biến ~ind~ và ban đầu khởi tạo ~ind = 1~ và mỗi lần duyệt thì ta sẽ flip biến ~ind~ là: ~ind = ind \oplus 1~.

Như vậy tại mỗi lần duyệt ta sẽ có ~f[ind][j]~ sẽ bằng tổng của số lượng tập con tại:

  • ~f[ind \oplus 1][j] \times (1 + \frac{c[v[i]]}{2})~ là số lượng tập con trước đó có tổng XOR là ~j~ nhân với ~1~ nửa số lượng số lần xuất hiện của ~v[i]~

  • ~f[ind \oplus 1][j \oplus v[i]] \times (\frac{1+c[v[i]]}{2})~ là số lượng tập con trước đó có tổng XOR là ~j \oplus v[i]~ nhân với ~1~ nửa số lần xuất hiện còn lại của ~v[i]~

Như vậy, công thức đầy đủ của ta sẽ là: ~f[ind \oplus 1][j] \times (1+\frac{c[v[i]]}{2}) + f[ind \oplus 1][j \oplus v[i]] \times (\frac{1+c[v[i]]}{2})~

Lưu ý: các phép toán cần thực hiện lấy dư cho ~10^9+7~ để tránh bị tràn.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.