Hướng dẫn giải bài toán: Đếm số hoán vị với điều kiện hiệu trị tuyệt đối

1. Mô tả bài toán

Cho hai số nguyên \(N\) và \(K\). Nhiệm vụ của bài toán là đếm số hoán vị của dãy số \([1, 2, \dots, N]\) sao cho với mọi cặp số kề nhau trong hoán vị, hiệu trị tuyệt đối giữa chúng không vượt quá \(K\). Cụ thể, với hoán vị \(p_1, p_2, \dots, p_N\), ta yêu cầu: \[ |p_i - p_{i+1}| \le K \quad \text{với mọi } 1 \le i < N. \]

2. Ý tưởng giải

Chúng ta sẽ sử dụng quy hoạch động (Dynamic Programming) với kỹ thuật Bitmask. Các bước ý tưởng như sau:

• Định nghĩa trạng thái:
  Gọi dp[mask][last] là số cách sắp xếp (hoán vị một phần) các số được đánh dấu trong mask sao cho số cuối cùng (vị trí cuối của dãy sắp xếp) là last. Ở đây:

  • mask là một bitmask gồm \(N\) bit, bit thứ \(i\) biểu thị xem số \(i+1\) đã được sử dụng chưa.
  • last là chỉ số (0-based) của phần tử đứng cuối cùng trong dãy.

• Tiền xử lý:
  Tạo một mảng adj[i][j] (kích thước \(N \times N\)) sao cho: \[ \text{adj}[i][j] = \text{true} \quad \text{nếu } |(i+1) - (j+1)| \le K. \] Mảng này giúp kiểm tra nhanh điều kiện giữa các phần tử khi nối thêm số mới.

• Khởi tạo:
  Với mỗi số \(i\) (từ 0 đến \(N-1\)), ta có trạng thái ban đầu: \[ dp[1 << i][i] = 1, \] tương ứng với hoán vị chỉ chứa số \(i+1\).

• Chuyển trạng thái:
  Với mỗi trạng thái hiện tại (mask, last), ta duyệt qua các số nxt chưa được sử dụng (nghĩa là bit nxt trong mask bằng 0). Nếu adj[last][nxt] là đúng (tức \(|(last+1) - (nxt+1)| \le K\)), ta cập nhật: \[ dp[mask \,|\, (1 << nxt)][nxt] += dp[mask][last]. \]

• Kết quả:
  Sau khi xét hết các trạng thái, kết quả là tổng các giá trị: \[ \text{ans} = \sum_{i=0}^{N-1} dp[(1 << N) - 1][i], \] với (1 << N) - 1 biểu diễn bitmask của tập đầy đủ các số.

3. Ví dụ minh họa

Xét \(N = 3\) và \(K = 1\). Các hoán vị của \([1,2,3]\) như sau:

1. \([1,2,3]\):

   • \(|1-2| = 1 \le 1\)
   • \(|2-3| = 1 \le 1\)
     → Hợp lệ

2. \([1,3,2]\):

   • \(|1-3| = 2 > 1\)
     → Không hợp lệ

3. \([2,1,3]\):

   • \(|2-1| = 1 \le 1\)
   • \(|1-3| = 2 > 1\)
     → Không hợp lệ

4. \([2,3,1]\):

   • \(|2-3| = 1 \le 1\)
   • \(|3-1| = 2 > 1\)
     → Không hợp lệ

5. \([3,1,2]\):

   • \(|3-1| = 2 > 1\)
     → Không hợp lệ

6. \([3,2,1]\):

   • \(|3-2| = 1 \le 1\)
   • \(|2-1| = 1 \le 1\)
     → Hợp lệ

Chỉ có 2 hoán vị hợp lệ: \([1,2,3]\) và \([3,2,1]\).

4. Phân tích độ phức tạp

• Số trạng thái:
  Có tổng số \(2^N\) bitmask và với mỗi bitmask có \(N\) trạng thái cuối, nên số trạng thái là \(O(N \times 2^N)\).

• Thao tác chuyển trạng thái:
  Mỗi trạng thái có thể chuyển qua tối đa \(N\) lựa chọn, do đó độ phức tạp tổng là \(O(N^2 \times 2^N)\).

• Với \(N \le 15\):
  Số trạng thái tối đa khoảng \(15 \times 2^{15} \approx 15 \times 32768 = 491520\), và số thao tác chuyển trạng thái xấp xỉ \(15^2 \times 32768 \approx 7 \times 10^6\) phép tính, đảm bảo chạy nhanh trong môi trường cạnh tranh.

5. Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        int N, K;
        cin >> N >> K;

        // Tiền tính mảng kề: adj[i][j] = true nếu |(i+1) - (j+1)| <= K
        vector<vector<bool>> adj(N, vector<bool>(N, false));
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(abs((i+1) - (j+1)) <= K) {
                    adj[i][j] = true;
                }
            }
        }

        // dp[mask][last]: số cách sắp xếp với tập số mask, kết thúc bằng số last (chỉ số 0-based)
        vector<vector<long long>> dp(1 << N, vector<long long>(N, 0LL));

        // Khởi tạo: mỗi số đứng một mình
        for(int i = 0; i < N; i++){
            dp[1 << i][i] = 1LL;
        }

        // Duyệt tất cả các trạng thái
        for(int mask = 0; mask < (1 << N); mask++){
            for(int last = 0; last < N; last++){
                if(dp[mask][last] == 0) continue;
                // Thử nối thêm các số chưa dùng
                for(int nxt = 0; nxt < N; nxt++){
                    if((mask & (1 << nxt)) == 0 && adj[last][nxt]) {
                        dp[mask | (1 << nxt)][nxt] += dp[mask][last];
                    }
                }
            }
        }

        // Kết quả: tổng số cách khi đã dùng hết các số (mask = (1<<N) - 1)
        long long ans = 0;
        for(int i = 0; i < N; i++){
            ans += dp[(1 << N) - 1][i];
        }

        cout << ans << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        int full_mask = (1 << N) - 1;
        vector<vector<long long>> dp(1 << N, vector<long long>(N + 1, 0));
        for (int i = 1; i <= N; ++i) {
            dp[1 << (i-1)][i] = 1;
        }
        vector<vector<int>> masks_by_bits(N + 1);
        for (int mask = 0; mask < (1 << N); ++mask) {
            int cnt = __builtin_popcount(mask);
            if (cnt >= 1 && cnt <= N) {
                masks_by_bits[cnt].push_back(mask);
            }
        }
        for (int s = 1; s < N; ++s) {
            for (int mask : masks_by_bits[s]) {
                for (int last = 1; last <= N; ++last) {
                    if (!(mask & (1 << (last - 1)))) continue;
                    if (dp[mask][last] == 0) continue;
                    for (int next_num = 1; next_num <= N; ++next_num) {
                        if (mask & (1 << (next_num - 1))) continue;
                        if (abs(last - next_num) > K) continue;
                        int new_mask = mask | (1 << (next_num - 1));
                        dp[new_mask][next_num] += dp[mask][last];
                    }
                }
            }
        }
        long long ans = 0;
        for (int last = 1; last <= N; ++last) {
            ans += dp[full_mask][last];
        }
        cout << ans << endl;
    }
    return 0;
}