Subtask 1: ~n \le 10^4~.

Ta duyệt mọi cặp vị trí ~i~, ~j~. Nếu cặp vị trí ~i~, ~j~ thỏa mãn điều kiện đề bài thì ta tăng biến kết quả lên ~1~ đơn vị.

Bài toán của chúng ta còn lại việc kiểm tra điều kiện ~\binom{a_i}{a_j}~ là chẵn.

Công thức tổ hợp chập ~r~ của ~n~: ~\binom{n}{r} = \frac{n!}{r!(n - r)!}~

Ta phân tích ~n! = 2^{k_n}d_n~ sao cho ~d_n~ là số lẻ.

Thay vào công thức tổ hợp chập, ta có: ~\binom{n}{r} \bmod 2 = \frac{n!}{r!(n - r)!} \bmod 2 = \frac{2^{k_n}d_n}{2^{k_r}d_r 2^{k_{n - r}}d_{n - r}} \bmod 2 = 2^{k_n - k_r - k_{n - r}} \bmod 2~.

Vậy, ~\binom{n}{r} \equiv 0 \pmod{2}~ khi và chỉ khi ~k_n - k_r - k_{n - r} \ne 0~.

~k_i~ có thể tính dựa trên công thức ~k_i = \sum_{p = 1}^\infty \lfloor \frac{i}{2^p} \rfloor = \lfloor \frac{i}{2} \rfloor + \sum_{p = 2}^\infty \lfloor \frac{i}{2^p} \rfloor = \lfloor \frac{i}{2} \rfloor + \sum_{p = 2}^\infty \lfloor \frac{\frac{i}{2}}{2^{p - 1}} \rfloor = \lfloor \frac{i}{2} \rfloor + \sum_{p = 1}^\infty \lfloor \frac{\frac{i}{2}}{2^{p}} \rfloor = \lfloor \frac{i}{2} \rfloor + k_{\lfloor \frac{i}{2} \rfloor}~.

Từ đây, ta có thể tính ~k_i, \forall i \in [0, 10^6]~ bằng quy hoạch động:

• Cơ sở: ~k_0 = 0~.

• Công thức đệ quy: ~k_i = k_{\lfloor \frac{i}{2} \rfloor} + \lfloor \frac{i}{2} \rfloor~.

Độ phức tạp: ~O(\max a_i + n^2)~.

Subtask 2: không có ràng buộc gì thêm.

Ta đi đếm số cặp ~i~, ~j~ cho ra kết quả ~\binom{a_i}{a_j}~ là lẻ.

Theo định lý Lucas, ~\binom{n}{r} \bmod p = \prod_{i = 0}^{k} \binom{n_i}{r_i} \bmod p~

Với ~p = 2~, ta có ~n_kn_{k-1}\ldots n_0~ là biểu diễn nhị phân của ~n~, ~r_kr_{k-1}\ldots r_0~ là biểu diễn nhị phân của ~r~, ~0 \le n_i, r_i \le 1, \forall i \in [0, k]~.

~\binom{n}{r}~ là lẻ khi và chỉ khi ~\binom{n_i}{r_i}~ lẻ với mọi ~i \in [0, k]~. Suy ra, ~\forall i \in [0, k]: r_i \le n_i~. Vậy ~n_k n_{k - 1} \ldots n_0~ là supermask của ~r_k r_{k - 1} \ldots r_0~. Từ đây, ta quy về bài toán DP SOS cơ bản, đếm số lượng cặp sao cho một số là supermask của một số khác.

Đặt ~cnt[x]~ là số lần xuất hiện của giá trị ~x~ trong mảng ~a[]~.

Ta tính ~f[mask] = \sum_{i \subseteq mask} cnt[i]~ bằng DP SOS.

Số cặp vị trí ~i~, ~j~ sao cho ~a_i \ge a_j~ và ~\binom{a_i}{a_j}~ lẻ là ~\sum_{i = 1}^n f[a_i]~.

Độ phức tạp: ~O(n + \max a_i \log_2 \max a_i)~