--- author: nguyencter tags: BPER title: BPER Solution --- $\Huge\text{BPER Solution}$ ------- :::info 🔗 Links: [Đề bài](https://drive.google.com/file/d/1xfPTrLMYT5HQY_0zB6Kvn3KzwAP0T0S4/view?usp=sharing) 📌 Tags: `dp` ✍️ Writer: nguyencter 📋 Content: [TOC] ::: ----- ## Giới Thiệu Đề Bài Với số nguyên dương $n$, một hoán vị của $1,2,...,n$ được gọi là hoán vị đẹp nếu viết liên tiếp hoán vị đó tạo thành một số nguyên chia hết cho $11$. **Yêu cầu:** Cho $n$, đếm số hoán vị đẹp. ----- ## Thuật toán *Nhận xét*: một số chia hết cho $11$ là tổng các kí tự ở vị trí lẻ trừ tổng các kí tự ở vị trí chẵn chia hết cho $11$. Nếu ta thêm một số có hai chữ số vào một hoán vị thì các số ở vị trí chẵn thì vẫn ở vị trí chẵn còn các số ở vị trí lẻ vẫn ở vị trí lẻ. ## Subtask 1: $\Large n < 10$. Ta duyệt qua tất cả các hoán vị và đếm số hoán vị chia hết cho $11$. Độ phức tạp $O(n!).$ ## Subtask 2: $\Large n < 20$. Gọi $f(i,du,le)$ là số hoán vị đẹp có được khi chèn $i$ vào $i-1$ vị trí trước đó khi có dư là $du$ và $le$ vị trí lẻ. Gọi $du$ là (tổng ở vị trí lẻ - tổng ở vị trí chẵn) $mod$ $11$. Gọi $le$ là số lượng ví trí lẻ. Gọi $a$ là chênh lệch giữa tổng trước và sau khi thêm số $i$ vào vị trí lẻ. - $\text{a = (i / 10 - i % 10 + 11) % 11}$ Gọi $b$ là chênh lệch giữa tổng trước và sau khi thêm số $i$ vào vị trí chẵn. - $\text{b = (i % 10 - i / 10 + 11) % 11}$ Hàm $f(i,le,du)$ được tính như sau: - Nếu $i>n$ thì $return (du==0)$. - Ngược lại $return$ $le*f(i+1,(du+a)$ % $11,le+1)$ + $(i-le)* f(i+1,(du-b+11)$%$11,le)$. Duyệt tất cả hoán vị từ $1$ đến $9$ với mỗi hoán vị $ans+=f(10,du,5)$. Kết quả bài toán là $ans$. Độ phức tạp $O(9!*2^n).$ ## Subtask 3 $\Large n < 100$. Gọi $dp[n][k][p]$ là số lượng các hoán vị của $n$ số tự nhiên đầu tiên mà có tổng các kí tự ở vị trí chẵn trừ tổng các kí tự ở vị trí lẻ chia dư cho $11$ bằng $k$ và hiện tại có $p$ vị trí lẻ có thể thêm các số vào các vị trí này. Nếu thêm các số có một chữ số vào hoán vị thì các vị trí chẵn lẻ có thể bị đảo lộn nên với các hoán vị có độ dài bé hơn 10 thì ta sẽ trâu hết tất cả các hoán vị rồi cập nhật vào mảng $dp$. Với $dp[n][k][p]$ với $n$ > $9$ ta có các trương hợp sau: - Gọi $a$ là chênh lệch giữa tổng trước và sau khi thêm số $n$ vào vị trí lẻ. - Gọi $b$ là chênh lệch giữa tổng trước và sau khi thêm số $n$ vào vị trí chẵn. - Ta có: - $\text{a = (n / 10 - n % 10 + 11) % 11}$ - $\text{b = (n % 10 - n / 10 + 11) % 11}$ - Nếu thêm số $n$ vào vị trí lẻ thì - $\text{dp[i][j][k] += dp[i - 1][(j - a + 11) % 11][k - 1] * (k - 1)}$ - Nếu thêm số $n$ vào vị trí chẵn thì - $\text{dp[i][j][k] += dp[i - 1][(j - b + 11) % 11][k] * (i - k)}$ Kết quả của bài toán là $\sum_{p = 0}^{n} dp[n][0][p]$. Độ phức tạp $O(9! + n^2 * 11)$. ---- Tham khảo code mẫu ở [đây](https://ideone.com/aCvYJC).