Editorial for Bedao Regular Contest 12 - XORPERM


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.

Authors: FireGhost130104 , bedao

Dễ thấy, các số ở hai mảng ~a~ và ~b~ luôn đi chung theo cặp, vì vậy ta sẽ chia ~n~ số thành ~2~ nhóm: nhóm ~X~ gồm các số ~a_i~ có ~b_i=1~ và nhóm ~Y~ gồm các số ~a_i~ có ~b_i=0~. Giả sử ~|X|=x~ và ~|Y|=y~ (~x + y = n~).

Với mọi hoán vị ~p=[p_1,p_2,…,p_n]~, trong nhóm ~X~ luôn tồn tại ~\lceil \frac{x}{2} \rceil~ số mang dấu ~+~ và ~\lfloor \frac{x}{2} \rfloor~ số mang dấu ~-~. Trong khi đó, ở nhóm ~Y~, số lượng số mang dấu ~+~ và dấu ~–~ lại không cố định mà phụ thuộc vào hoán vị ~p~.

Xét tập ~Y~: dễ thấy, ~a_{p_i}~ sẽ mang dấu ~+~ nếu số bit ~1~ trong đoạn ~b_{p_1},b_{p_2},\ldots,b_{p_{i - 1}}~ là chẵn; và mang dấu ~–~ nếu số bit 1 trong đoạn ~b_{p_1},b_{p_2},\ldots,b_{p_{i - 1}}~ là lẻ.

Ta sẽ có được cách làm như sau: Xét mảng ~b_{p_1},b_{p_2},\ldots,b_{p_{n}}~, dễ thấy mảng này luôn có dạng

~\ldots\ |1|\ldots |1| \ldots |1| \ldots~

với ~\ldots~ là chuỗi các bit ~0~.

Gọi các khoảng ~\ldots~ này là ~1~ túi. Ta định nghĩa ~1~ túi là túi dương nếu chúng nằm sau một lượng lẻ bit ~1~, và túi âm nếu chúng nằm sau một lượng chẵn bit ~1~. Dễ thấy ta có ~\lceil \frac{x}{2} \rceil~ túi dương và ~\lceil \frac{x + 1}{2} \rceil~ túi âm. Nếu ~b_{p_i}~ nằm trong túi dương, ~a_{p_i}~ sẽ mang dấu ~+~ và ngược lại, nếu ~b_{p_i}~ nằm trong túi âm, ~a_{p_i}~ sẽ mang dấu ~-~.

Đây chính là bài toán chia kẹo Euler (stars-and-bars): nếu trong tập ~Y~ có ~z~ số mang dấu ~+~, ta sẽ bỏ ~z~ số này vào ~\lceil \frac{x}{2} \rceil~ túi dương, và bỏ ~y- z~ số còn lại vào ~\lceil \frac{x + 1}{2} \rceil~ túi âm. Ngoài ra, vì thứ tự của các số này là quan trọng, số cách sắp xếp cuối cùng sẽ là:

~\displaystyle \binom{z + \lceil \frac{x}{2} \rceil - 1}{\lceil \frac{x}{2} \rceil - 1} \cdot z! \cdot \binom{y -z + \lceil \frac{x+1}{2} \rceil - 1}{\lceil \frac{x+1}{2} \rceil - 1} \cdot (y - z)!~

Giả sử ta chia tập ~X~ thành ~2~ phần (mỗi phần lần lượt có ~\lceil \frac{x}{2} \rceil~ và ~\lfloor \frac{x}{2} \rfloor~ phần tử), và hiệu của ~2~ phần này đồng dư với ~r (\text{mod k})~ (có ~f[r]~ cách). Khi ấy, chúng ta sẽ đếm số cách chia tập ~Y~ thành ~2~ phần (mỗi phần lần lượt có ~z~ và ~y - z~ phần tử, ~0 \le z \le y~), và hiệu của ~2~ phần này đồng dư với ~k-r (\text{mod k})~ (có ~g[z][k - r]~ cách). Việc đếm số cách chia này có thể dễ dàng xử lý bằng quy hoạch động knapsack.

Số cách sắp xếp cho mỗi trường hợp như trên sẽ là:

~\displaystyle f[r] \cdot \lceil \frac{x}{2} \rceil ! \cdot \lfloor \frac{x}{2} \rfloor ! \cdot g[z][k - r] \cdot \binom{z + \lceil \frac{x}{2} \rceil - 1}{\lceil \frac{x}{2} \rceil - 1} \cdot z! \cdot \binom{y - z + \lceil \frac{x+1}{2} \rceil - 1}{\lceil \frac{x+1}{2} \rceil - 1} \cdot (y - z)!~

Đáp án của bài toán là tổng của tất cả các trường hợp.

Độ phức tạp: ~O(kn^2)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.