Tóm tắt đề bài

Cho số nguyên dương \(n\). Một hoán vị của tập hợp \(\{1, 2, \dots, n\}\) được gọi là hoán vị đẹp nếu khi viết các số trong hoán vị liên tiếp nhau theo thứ tự, ta nhận được một số nguyên chia hết cho \(11\). Hãy đếm số lượng hoán vị đẹp như vậy, kết quả lấy dư cho \(10^9 + 7\).

Phân tích

Dấu hiệu chia hết cho 11

Một số nguyên chia hết cho \(11\) khi và chỉ khi hiệu giữa tổng các chữ số ở vị trí lẻ và tổng các chữ số ở vị trí chẵn chia hết cho \(11\).
Khi ghép các số \(x_1, x_2, \dots, x_n\) lại với nhau, vị trí của các chữ số trong số \(x_i\) phụ thuộc vào tổng độ dài của các số đứng trước nó (\(x_1, \dots, x_{i-1}\)).

• Nếu tổng độ dài của các số trước \(x_i\) là số chẵn, các chữ số ở vị trí lẻ của \(x_i\) vẫn nằm ở vị trí lẻ trong số lớn, và tương tự với vị trí chẵn.
• Nếu tổng độ dài của các số trước \(x_i\) là số lẻ, các chữ số ở vị trí lẻ của \(x_i\) sẽ chuyển sang vị trí chẵn trong số lớn, và ngược lại.

Phân loại các số

Để đơn giản hóa, ta chia các số từ \(1\) đến \(n\) thành hai loại dựa trên độ dài (số chữ số) của chúng:

1. Loại lẻ: Các số có số chữ số là số lẻ (ví dụ: \(1, 234, 10001\)). Khi đặt một số loại này vào dãy, nó sẽ làm thay đổi tính chẵn lẻ của vị trí các chữ số cho tất cả các số đứng sau nó.
2. Loại chẵn: Các số có số chữ số là số chẵn (ví dụ: \(12, 1023\)). Khi đặt một số loại này vào dãy, nó không làm thay đổi tính chẵn lẻ của vị trí các chữ số cho các số đứng sau.

Gọi \(S(x)\) là giá trị đóng góp của số \(x\) vào tổng hiệu (tổng lẻ - tổng chẵn).

• Nếu \(x\) đứng sau một lượng chữ số có tổng độ dài là chẵn: đóng góp là \(S(x)\).
• Nếu \(x\) đứng sau một lượng chữ số có tổng độ dài là lẻ: đóng góp là \(-S(x)\).

Hướng giải quyết

Bước 1: Tiền xử lý

• Với mỗi số \(i \in [1, n]\), tính độ dài \(len(i)\) và giá trị đóng góp \(val(i)\) (tổng chữ số vị trí lẻ - tổng chữ số vị trí chẵn).
• Chia các số thành hai nhóm: nhóm odd_len (độ dài lẻ) và nhóm even_len (độ dài chẵn).

Bước 2: Quy hoạch động cho nhóm odd_len

Giả sử có \(m\) số thuộc nhóm odd_len. Khi xếp \(m\) số này vào hoán vị, sẽ có \(\lceil m/2 \rceil\) số ở vị trí mà trước nó có tổng độ dài là chẵn, và \(\lfloor m/2 \rfloor\) số ở vị trí mà trước nó có tổng độ dài là lẻ (do các số độ dài chẵn không làm thay đổi tính chất này).

• Gọi \(f[i][j][rem]\) là số cách chọn \(j\) số từ \(i\) số đầu tiên của nhóm odd_len sao cho tổng giá trị đóng góp của chúng chia \(11\) dư \(rem\).
• Công thức chuyển trạng thái:
  
  \[ f[i][j][rem] = f[i-1][j][(rem - (-val(a_i)) + 11) \pmod{11}] + f[i-1][j-1][(rem - val(a_i) + 11) \pmod{11}] \]
• Sau khi tính xong, ta có số cách chọn vị trí cho nhóm lẻ. Đừng quên nhân với \(k!\) và \((m-k)!\) để tính số hoán vị trong nội bộ nhóm.

Bước 3: Quy hoạch động cho nhóm even_len

Các số có độ dài chẵn không làm thay đổi tính chẵn lẻ của các vị trí phía sau. Do đó, dù ta chèn chúng vào bất kỳ vị trí nào trong dãy các số odd_len đã xếp, giá trị đóng góp của chúng chỉ phụ thuộc vào việc trước nó có bao nhiêu số odd_len.

• Nếu chèn vào sau một số lượng lẻ các số odd_len, giá trị đóng góp là \(-val(x)\). Ngược lại là \(val(x)\).
• Gọi \(dp[i][j][rem]\) là số cách chèn \(i\) số đầu tiên của nhóm even_len, với \(j\) số được chèn vào các vị trí có hệ số dương, tổng dư là \(rem\).
• Số lượng vị trí có hệ số dương và âm được xác định bởi số lượng số odd_len.

Bước 4: Kết hợp

Kết quả cuối cùng là tổng các cách kết hợp hai nhóm sao cho tổng dư cuối cùng bằng \(0\).

Độ phức tạp

• Tiền xử lý: \(O(n \log n)\)
• Quy hoạch động: \(O(n^2 \cdot 11)\)
• Tổng độ phức tạp: \(O(n^2)\), phù hợp với \(n = 100\).

Code tham khảo

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

long long MOD = 1e9 + 7;
long long f[105][105][11], dp[105][105][11];
long long fact[105];

int main() {
    int n;
    cin >> n;
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;

    vector<int> odd_len, even_len;
    for (int i = 1; i <= n; i++) {
        string s = to_string(i);
        int val = 0;
        for (int j = 0; j < s.size(); j++) {
            if (j % 2 == 0) val += (s[j] - '0');
            else val -= (s[j] - '0');
        }
        val = (val % 11 + 11) % 11;
        if (s.size() % 2 != 0) odd_len.push_back(val);
        else even_len.push_back(val);
    }

    // DP cho nhóm độ dài lẻ
    int m = odd_len.size();
    f[0][0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= i; j++) {
            for (int r = 0; r < 11; r++) {
                if (!f[i][j][r]) continue;
                // Số này ở vị trí hệ số dương
                f[i + 1][j + 1][(r + odd_len[i]) % 11] = (f[i + 1][j + 1][(r + odd_len[i]) % 11] + f[i][j][r]) % MOD;
                // Số này ở vị trí hệ số âm
                f[i + 1][j][(r - odd_len[i] + 11) % 11] = (f[i + 1][j][(r - odd_len[i] + 11) % 11] + f[i][j][r]) % MOD;
            }
        }
    }

    int pos_slots = (m + 1) / 2;
    int neg_slots = m / 2;

    // DP cho nhóm độ dài chẵn
    int k = even_len.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j <= i; j++) {
            for (int r = 0; r < 11; r++) {
                if (!dp[i][j][r]) continue;
                // Chèn vào vị trí hệ số dương (có pos_slots vị trí)
                dp[i + 1][j + 1][(r + even_len[i]) % 11] = (dp[i + 1][j + 1][(r + even_len[i]) % 11] + dp[i][j][r] * (pos_slots + j)) % MOD;
                // Chèn vào vị trí hệ số âm (có neg_slots vị trí)
                dp[i + 1][j][(r - even_len[i] + 11) % 11] = (dp[i + 1][j][(r - even_len[i] + 11) % 11] + dp[i][j][r] * (neg_slots + (i - j))) % MOD;
            }
        }
    }

    long long ans = 0;
    for (int r = 0; r < 11; r++) {
        long long ways_odd = (f[m][pos_slots][r] * fact[pos_slots]) % MOD;
        ways_odd = (ways_odd * fact[neg_slots]) % MOD;

        int target_r = (11 - r) % 11;
        for (int j = 0; j <= k; j++) {
            long long ways_even = dp[k][j][target_r];
            ans = (ans + ways_odd * ways_even) % MOD;
        }
    }

    cout << ans << endl;
    return 0;
}