Nguồn bài: https://atcoder.jp/contests/arc116/tasks/arc116_d

Tóm tắt: Cho hai số ~N, M~. Đếm số dãy ~A~ độ dài ~N~ gồm các số nguyên không âm thỏa mãn:

• ~A_1 + A_2 + \ldots + A_N = M~.
• ~A_1 \oplus A_2 \oplus \ldots \oplus A_N = 0~.

Subtask 1 (5p) ~N = 2~

Trường hợp duy nhất để ~A_1 \oplus A_2 = 0~ là ~A_1 = A_2~, từ đây suy ra nếu ~M~ chẵn ta sẽ có một cách chọn ~[M/2, M/2]~, nếu không thì không có cách chọn.

ĐPT: ~O(1)~

Subtask 2 (21p) ~N, M \le 100~

Ta sử dụng đệ quy có nhớ: ~f(i, s, x)~ là số cách chọn khi xét ~i~ số đầu, tổng là ~s~ và tổng XOR là ~x~. Đáp án là ~f(N, M, 0)~.

ĐPT: ~O(N^2 M^2)~

Subtask 3 (28p) ~M \le 20~

Ta duyệt nhị phân, tìm các cách chọn dãy có các phần tử nguyên dương thỏa mãn tổng bằng ~M~ và tổng XOR bằng ~0~. Khi đó gọi số lượng phần tử hiện tại là ~i~, ta sẽ phải xếp ~N - i~ số ~0~ còn lại vào dãy ~A~ để đủ ~N~ phần tử. Cách xếp ~N - i~ phần tử vào ~N~ phần tử hiển nhiên là ~\displaystyle \binom{N}{N - i}~.

Bằng cách tính trước các mảng cần thiết, ta có thể tìm ~\displaystyle \binom{N}{N - i}~ trong ~O(1)~.

ĐPT: ~O(2^M)~.

Subtask 4 (30p) ~N, M \le 5000~

Gọi ~cnt_i~ là số lượng số có bit ~i~ bật trong dãy ~A~. Vì ~A_1 \oplus A_2 \oplus \ldots \oplus A_N = 0~ nên ~cnt_i~ phải chẵn với mọi ~i~. Khi đó ta có thể tưởng tượng là đang xây dựng dãy ~A~ lên dần theo từng bit một: cụ thể ta sẽ quy hoạch động như sau:

• Gọi ~f(k, c)~ là số cách tạo ra ~N~ số, trong đó bit hiện tại ta đang xây dựng là ~k~ và tổng hiện tại là ~c~. Ban đầu ta có ~f(0, 0) = 1~.
• Khi xét đến bit ~k~, ta có thể có ~i = 2, 4, 6, \ldots~ các số có bit ~k~ bật. Việc xếp xem số nào sẽ có bit ~k~ bật trong số ~N~ phần tử thì sẽ có tổng cộng là ~\displaystyle \binom{N}{i}~ cách, và tổng ~c~ sẽ tăng lên ~2^k \times i~. Khi đó ta có công thức chuyển vị như sau:
  • ~\displaystyle f(k + 1, c + 2^k \times i) += f(k, c) \times \binom{N}{i}~
• Đáp án cuối cùng là ~f(\log M + 1, M)~, do ta chỉ cần tính đến đây là đủ vì ~2^{\log M + 1} > M~.

Chú ý là khi ta duyệt các ~i = 2, 4, 6, \ldots~, ta chỉ duyệt các ~i~ thỏa mãn ~i \times 2^k \le M~ để tiết kiệm thời gian. Khi đó tổng số lần duyệt ~i~ là ~\frac{M}{2} + \frac{M}{4} + \frac{M}{8} \ldots < M~

ĐPT: ~O(M^2 \times \log M)~

Subtask 5 (16p) ~N, M \le 10^5~

Chú ý công thức chuyển vị ở Subtask 4:

• ~\displaystyle f(k + 1, c + 2^k \times i) += f(k, c) \times \binom{N}{i}~

Đặt ~a_x = f(k, x)~, ~\displaystyle b_{2^k \times x} = \binom{N}{x}~, ~c_x = f(k + 1, x)~. Khi đó ta có:

• ~\displaystyle c_x = \sum_{i + j = x}a_i b_j~. Đây chính là áp dụng quen thuộc của FFT. Từ đó ta có thuật toán với độ phức tạp ~O(M \times \log^2 M)~.

Thực tế, khi cài đặt thì thuật toán sẽ chạy khá chậm do FFT dù là thuật toán ~O(n \log n)~ nhưng có hằng số khá cao.