\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Chúng ta sẽ sinh lần lược các hoán vị và đếm số lượng cặp nghịch thế

Ta sẽ dùng \(backtracking\) để sinh ra các hoán vị

Hoặc có thể sử dụng hàm sinh hoán vị tiếp theo (trong C++ là std::next_permutation())

• Phần xử lí là đếm số dãy nghịch thế của hoán vị \(perm\)

Ta sẽ duyệt các cặp \((l, r)\) thỏa \(1 \leq l < r \leq n\) và tăng biến đếm lên khi nó nghịch thế (\(l < r\) nhưng \(perm_l > perm_r\))

Kết quả bài toán là số lần biến đếm của \(k\) hoán vị kể từ hoán vị \(\pi\) bằng \(m\)

\(\color{green}{\text{Preference TLE Code }}\): Brute-force

\(^{^{\color{purple}{\text{Complexity : }} O(n! \times n^2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

int n, m;
int inversion_count(const vector<int> &perm)
{
    int res = 0;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (perm[i] < perm[j])
                res++;

    return res;
}

int main()
{
    cin >> n >> m;

    vector<int> perm(n + 1);
    for (int i = 1; i <= n; ++i)
        perm[i] = i;   

    int res = 0;
    do {
        if (inversion_count(perm) == m)
            res++;

    } while (next_permutation(1 + all(perm)));
    cout << res;
}

\(\color{orange}{\text{Hint 2 <Optimization>}}\)

• Chúng ta có thể tính số lượng cặp nghịch thế nhanh hơn (tham khảo bài này) trong \(O(n \log n)\) và xử lí toàn bộ trong \(O(n! \times n \log alphabet)\) nhưng thế vẫn chẳng thể giúp AC bài này vì \(n!\) tăng rất nhanh

\(\color{orange}{\text{Hint 3 <Pattern-finding> <Dynamic-Programming>}}\)

• Sử dụng thuật toán trên đễ xuất ra các dãy số và tìm quy luật

Với dãy n = ?: f[0], f[1], ... và \(f[m]\) là số lần xuất hiện hoán vị bậc \(n\) có \(m\) cặp nghịch thế

Quy luật

• [0] Độ dài dãy \(f[n]\) là \(f[n]\) là \(\frac{n \times (n - 1)}{2}\)

• [1] Dãy này đối xứng nhau

• [2] Độ dài dãy thứ \(n + 1\) sẽ nhiều hơn \(n\) phân tử so với dãy \(n\)

• [3] Từ dãy trước (\(n - 1\)) có thể tạo ra dãy sau (\(n\))

Gọi \(prev[]\) là dãy trước

Gọi \(curr[]\) là dãy

Khi \(m < n\) thì \(curr[m] = curr[m - 1] + prev[m]\)

Khi \(m \geq n\) thì \(curr[m] = curr[m - 1] + prev[m] - prev[m - n]\)

Chứng minh

• Có thể xem ở đây bản tiếng anh

• Xét các trường hợp đặc biệt

Trong trường hợp hoán vị giảm dân từ \(n \rightarrow 1\) thì có \(\frac{n \times (n - 1)}{2} - 1\) cặp nghịch thế

Trong trường hợp hoán vị tăng dần từ \(1 \rightarrow n\) thì có \(0\) cặp nghịch thế

• Nên có tất cả \(\frac{n \times (n - 1)}{2}\) các số lượng cặp nghịch thế khác nhau trong tất cả các hoán vị bậc \(n\) (Chứng minh [0] thành công)

• Số lượng hoán vị có \(m\) cặp nghịch thế = Số lượng hoán vị không có \(m\) cặp nghịch thế (Chứng minh [1] thành công)

• Gọi \(f[n][k]\) là số lượng dãy hoán vị bậc \(n\) có \(k\) cặp nghịch thế

Khi \(k = 0\) thì \(f[n][0] = 1\) (dãy hoán vị tăng dần)

Khi \(n = 0\) thì \(f[0][k] = 0\) (không tồn tại dãy hoán vị thì không có cặp nghịch thế)

Lưu ý rằng \(f[0][0] = 1\) vì tập rỗng không có cặp nghịch thế

• Xét \(f[4][k]\)

$$$
f[4] = {1, 3, 5, 6, 5, 3, 1}

|k=0|k=1|k=2|k=3|k=4|k=5|k=6|
| 1234 | 1243 | 1342 | 1432 | 2431 | 3421 | 4321 |
| | 1324 | 1423 | 2341 | 3241 | 4231 | |
| | 2134 | 2143 | 2413 | 3412 | 4312 | |
| | | 2314 | 3142 | 4132 | | |
| | | 3124 | 3214 | 4213 | | |
| | | | 4123 | | | |
| | | | | | | |
| 1 | 3 | 5 | 6 | 5 | 3 | 1 |
| | | | | | | |
$$$

• Giờ ta cần tìm \(f[5][k]\), thì ta sẽ chèn số \(5\) vào bất kì vị trí nào trong các dãy hoán vị

Vì \(5\) là số lớn nhất trong các số \([1..4]\)

Ta có thể chọn chỗ chèn để nó thêm các cặp nghịch thế

Vì ta có 4 cách chọn nên \(f[5]\) sẽ có nhiều hơn 4 phần tử so với \(f[4]\) (Chứng minh [2] thành công)

• Giả sử cần tìm \(f[5][4]\), ta có thể chèn như sau

• Giả sử cần tìm \(f[5][5]\), ta có thể chèn như sau

• Vậy \(f[n][k] = sum(f[n - 1][k - n \rightarrow k - 1])\) (chứng minh [3] xong)

\(\color{green}{\text{Preference TLE Code }}\): Recursive Dynamic Programming

\(^{^{\color{purple}{\text{Complexity : }} O(n ^ 2 \times k)\ \color{purple}{\text{time}}\ ||\ O(n \times k)\ \color{purple}{\text{memory}}}}\)

/// Dua tren chung minh [3]

vector<vector<int> > f;
int solve(int n, int k)
{
    if (f[n][k] != -1) return f[n][k];
    if (k == 0) return f[n][0] = 1;
    if (n == 0) return f[0][k] = 0;

    f[n][k] = 0;
    for (int x = 0; n > x && k >= x; ++x)
    {
        f[n][k] += solve(n - 1, k - x);
        if (f[n][k] >= MOD) f[n][k] -= MOD;
    }

    return f[n][k];
}

int main()
{
    int n, k;
    cin >> n >> k;

    int total = n * (n - 1) / 2;
    if (k < 0 || k > total)
    {
        cout << 0;
        return 0;
    }

    f.assign(n + 1, vector<int>(k + 1, -1));
    cout << solve(n, k);
    return 0;
}

\(\color{orange}{\text{Hint 4 <Time-Optimization>}}\)

• Ta tối ưu thuật toán bằng nhận xét từ chứng minh [1] đó là \(f[n][k] = f[n][total - k]\) với \(total = \frac{n \times (n - 1)}{2}\)

• Ta cũng có thể biến đổi một chút bằng đảo nhãn

Thay vì \(f[n][k]\) lưu số lần xuất hiện hoán vị \(n\) có \(k\) cặp nghich thế

Thì ta sử dụng \(g[n][k]\) là số lần xuất hiện hoán vị \(n\) có không quá \(k\) cặp nghịch thế

Khi đó \(g[n][k] = sum(f[n][0..k])\)

Từ đó ta tính được \(g[n][k] = g[n][k - 1] + f[n][k] - f[n][k - n]\)

\(\color{green}{\text{Preference AC Code }}\): Recursive Dynamic Programming, Branch-and-bound

\(^{^{\color{purple}{\text{Complexity : }} O(n \times k)\ \color{purple}{\text{time}}\ ||\ O(n \times k)\ \color{purple}{\text{memory}}}}\)

/// Dua tren chung minh [1] [3]

vector<vector<int> > f;
int solve(int n, int k)
{
    int total = n * (n - 1) / 2;
    minimize(k, total - k);
    if (k < 0) return 0;
    if (f[n][k] != -1) return f[n][k];
    if (k == 0) return f[n][0] = 1;
    if (n == 0) return f[0][k] = 0;
    return f[n][k] = (solve(n, k - 1) + solve(n - 1, k) - solve(n - 1, k - n) + MOD) % MOD;
}

int main()
{
    int n, k;
    cin >> n >> k;

    int total = n * (n - 1) / 2;
    minimize(k, total - k);
    if (k < 0)
    {
        cout << 0;
        return 0;
    }

    f.assign(n + 1, vector<int>(k + 1, -1));
    cout << solve(n, k);
    return 0;
}

\(\color{orange}{\text{Hint 5 <Space-Optimization>}}\)

• Nhận xét rằng ta có thể tính \(f[n]\) trực tiếp từ \(f[n - 1]\) thì không việc gì phải lưu các dãy \(f[n - 2..0]\)

\(\color{green}{\text{Preference TLE Code }}\): Iterative Dynamic Programming

\(^{^{\color{purple}{\text{Complexity : }} O(n \times k)\ \color{purple}{\text{time}}\ ||\ O(k)\ \color{purple}{\text{memory}}}}\)

/// Dua tren chung minh [0] [1] [2] [3]

int main()
{
    int n, m;
    cin >> n >> m;

    int total = n * (n - 1) / 2;
    minimize(m, total - m);

    vector<int> prev;
    for (int itr = 1, len = 1; itr <= n; len += itr++)
    {
        vector<int> curr(len);
        curr.front() = 1;
        for (int i = 1; i < prev.size(); ++i)
        {
            curr[i] = (curr[i - 1] + prev[i]) % MOD;
            if (i >= itr)
                curr[i] = (curr[i] - prev[i - itr] + MOD) % MOD;
        }

        for (int i = 0; i < len / 2; ++i)
            curr[len - i - 1] = curr[i];

        swap(prev, curr);
    }

    cout << prev[m];
    return 0;
}

\(\color{orange}{\text{Hint 6 <Time-Optimization> <Space-Optimization>}}\)

• Nhận xét rằng ta chỉ cần duyệt đến \(m\) chứ không cần duyệt hết cả mảng

Thay vì duyệt \(f[0..n][0..total]\) với \(total = \frac{n \times (n - 1)}{2}\)

Ta chỉ cần duyệt \(f[0..n][0..k]\) và không quan tâm \(f[n - 2..0]\) khi đã duyệt, và cũng sẽ không duyệt tới \(f[k + 1..total]\)

\(\color{green}{\text{Preference AC Code }}\): Iterative Dynamic Programming

\(^{^{\color{purple}{\text{Complexity : }} O(n \times k)\ \color{purple}{\text{time}}\ ||\ O(k)\ \color{purple}{\text{memory}}}}\)

/// Dua tren chung minh [0] [1] [2] [3]
int main()
{
    int n, m;
    cin >> n >> m;

    int total = n * (n - 1) / 2;
    minimize(m, total - m);
    if (m < 0)
    {
        cout << 0;
        return 0;
    }

    int f[n + 1][m + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) f[0][i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        f[cur][0] = 1;
        for (int j = 1; j <= m; ++j)
        {
            f[cur][j] = f[cur][j - 1] + f[pre][j];
            if (f[cur][j] >= MOD) f[cur][j] -= MOD;

            if (j >= i)
            {
                f[cur][j] -= f[pre][j - i];
                if (f[cur][j] < 0) f[cur][j] += MOD;
            }
        }
    }

    cout << f[n & 1][m];
    return 0;
}