Cho một đồ thị hai phía, cần đếm số chu trình \(4\) của đồ thị

Subtask 1: \(n \leq 50\)

Xét tất cả các bộ \(4\) có thể có rồi kiểm tra.

Độ phức tạp: \(\mathcal{O}(n^{4})\).

Subtask 2: \(n \leq 300\)

Xét các bộ hai bạn nam \((x, y)\). Gọi \(k\) là số bạn nữ có thể nhảy cùng cả \(x\) lẫn \(y\), khi đó ta có thêm \(\dfrac{k \times (k - 1)}{2}\) cách chọn.

Độ phức tạp: \(\mathcal{O}(n^{3})\).

Subtask 3: \(n \leq 1000, m \leq 20000\)

Cải tiến subtask 2 bằng cách sử dụng bitset để tính nhanh số \(k\) cho từng cặp \((x, y)\)

Subtask 4: \(n \leq 5000, m \leq 20000\)

Cải tiến subtask 2 để tính nhanh \(k\) cho mọi cặp \((x, y)\) như sau: Xét các bộ ba \((a, b, c)\) sao cho bạn nữ \(b\) có thể nhảy cùng cả hai bạn nam \(a\) và \(c\), tăng biến đếm \(k[a][c]\). Để xét được hết các bộ ba, ta xét \(b\) trước rồi xét \(a\) và \(c\) chạy trong tập các bạn nhảy của \(b\).

Độ phức tạp: \(\sum_{x = 1}^{n} deg(x)^{2} \leq n \times \sum_{x = 1}^{n} deg(x) = \mathcal{O}(n \times m)\).

Subtask 5: không có rằng buộc gì thêm

Gọi \(G\) là tập các bạn nữ có số bạn nhảy lớn hơn \(\sqrt{m}\), \(g\) là tập các bạn nữ còn lại. Khi đó số bạn nữ thuộc \(G\) là không quá \(2 \times \sqrt{m}\), còn các bạn nữ thuộc \(g\) thì có không quá \(\sqrt{m}\) bạn nhảy. Ta sẽ đếm theo các trường hợp sau:

• Cả hai bạn nữ được chọn đều thuộc \(g\): Xóa hết các đỉnh thuộc \(G\) đi và làm như subtask 4. Độ phức tạp là tổng bình phương bậc đỉnh, lúc này không quá \(\mathcal{O}(\sqrt{m} \times m)\).

• Có ít nhất \(1\) bạn nữ được chọn thuộc \(G\): Xét \(z\) thuộc \(G\), xóa hết các bạn nam không nhảy cùng được với \(z\). Gọi \(deg[t]\) là số bạn nam có thể nhảy cùng bạn nữ \(t\), khi đó số cách chọn mà có chọn hai bạn nữ \((z, t)\) là \(\dfrac{deg[t] \times (deg[t] - 1)}{2}\). Với mỗi \(z\) cần dựng lại đồ thị, do đó độ phức tạp là \(\mathcal{O}(|G| \times (m + n)) = \mathcal{O}(\sqrt[m] \times (m + n))\)