Vấn đề A: Tối ưu hóa trên cây bằng thuật toán tham lam và cấu trúc hợp nhất tập hợp rời rạc

Mức độ: Trung bình đến Khó

Bài toán yêu cầu tối đa hóa một giá trị tổng bằng cách lựa chọn các nút trên cây. Giá trị của một nút được tính dựa trên giá trị gốc của nó và vị trí của nó trong chuỗi lựa chọn.

Ý tưởng chính:

• Sử dụng chiến lược tham lam. Ban đầu, mỗi nút được coi là một nhóm độc lập.
• Trong mỗi bước, chúng ta hợp nhất hai nhóm. Tiêu chí hợp nhất được xác định bằng cách so sánh tỷ lệ giữa tổng giá trị gốc (sumOfRawValues) và kích thước (groupSize) của các nhóm. Cụ thể, khi xem xét hợp nhất nhóm A (kích thước \(s_A\), tổng giá trị gốc \(m_A\)) và nhóm B (kích thước \(s_B\), tổng giá trị gốc \(m_B\)), thứ tự tối ưu được xác định bằng cách so sánh \(m_A \cdot s_B\) và \(m_B \cdot s_A\). Tiêu chí này thường xuất hiện trong các bài toán sắp xếp để tối ưu hóa tổng trọng số theo vị trí. Trong cài đặt này, nhóm có tỷ lệ \(sumOfRawValues / groupSize\) lớn hơn sẽ được ưu tiên xử lý (được coi là "tốt hơn" để hợp nhất trước).
• Cấu trúc DSU (Disjoint Set Union) được sử dụng để quản lý việc hợp nhất các nhóm một cách hiệu quả.
• Một hàng đợi ưu tiên (priority queue) được dùng để lưu trữ các nhóm hiện có. Hàng đợi này sẽ luôn cung cấp nhóm "tốt nhất" để hợp nhất dựa trên toán tử so sánh đã định nghĩa.
• Thuật toán DFS (Depth-First Search) được sử dụng để thiết lập cây và xác định nút cha ban đầu cho mỗi nút, phục vụ cho quá trình hợp nhất.
• Mỗi khi một nhóm được hợp nhất vào nhóm cha của nó, thông tin của nhóm cha sẽ được cập nhật (tổng giá trị gốc, tổng điểm tích lũy, kích thước), và nhóm cha đã cập nhật sẽ được đẩy lại vào hàng đợi ưu tiên.

Độ phức tạp:

Khoảng \(O(R \cdot N \log N)\), trong đó \(R\) là số lần gọi hàm giải quyết (số nút gốc có thể có), \(N\) là số nút trong cây. Mỗi thao tác hợp nhất DSU và hàng đợi ưu tiên mất \(\log N\) (hoặc \(\alpha(N)\) với nén đường và hợp nhất theo thứ hạng).

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <numeric> 
#include <queue>
#include <cstring> 

#define LL long long
#define MAX_NODES 30010

// Cấu trúc để lưu trữ thông tin của một nhóm các nút đã hợp nhất
struct GroupInfo {
    LL groupId;         // ID của nút đại diện cho nhóm (root trong DSU)
    LL accumulatedScore; // Tổng điểm tích lũy của nhóm (giá trị đã được nhân với vị trí)
    LL sumOfRawValues;   // Tổng giá trị gốc của các nút trong nhóm
    LL groupSize;        // Kích thước của nhóm

    // Toán tử so sánh cho hàng đợi ưu tiên (priority_queue mặc định là max-heap)
    // Ưu tiên nhóm có tỷ lệ sumOfRawValues / groupSize lớn hơn
    bool operator<(const GroupInfo& other) const {
        return sumOfRawValues * other.groupSize > other.sumOfRawValues * groupSize;
    }
    
    // Toán tử so sánh khác để kiểm tra tính hợp lệ của phần tử trong hàng đợi
    // Dùng để phát hiện các mục lỗi thời trong hàng đợi
    bool operator!=(const GroupInfo& other) const {
        return (groupId != other.groupId || 
                accumulatedScore != other.accumulatedScore || 
                sumOfRawValues != other.sumOfRawValues || 
                groupSize != other.groupSize);
    }
};

LL N_nodes; // Số lượng nút
LL nodeValues[MAX_NODES]; // Giá trị gốc của mỗi nút
LL isRootCandidate[MAX_NODES]; // Mảng đánh dấu nút có thể là gốc
LL parentOfNode[MAX_NODES]; // Nút cha của một nút trong cây DFS
LL dsuParent[MAX_NODES]; // Mảng cha cho cấu trúc DSU
std::vector<int> adjList[MAX_NODES]; // Danh sách kề cho cây
GroupInfo groupData[MAX_NODES]; // Mảng lưu thông tin cập nhật của các nhóm
std::priority_queue<GroupInfo> groupQueue; // Hàng đợi ưu tiên

// DFS để xây dựng cây và gán nút cha
void buildParentTree(int u, int p) {
    parentOfNode[u] = p;
    for (int v : adjList[u]) {
        if (v == p) continue;
        buildParentTree(v, u);
    }
}

// Tìm nút đại diện của một tập hợp trong DSU (có nén đường)
LL findSet(LL i) {
    if (i == dsuParent[i])
        return i;
    return dsuParent[i] = findSet(dsuParent[i]);
}

// Hợp nhất hai tập hợp trong DSU (không dùng union by rank/size để đơn giản)
void unionSets(LL i, LL j) {
    LL rootI = findSet(i);
    LL rootJ = findSet(j);
    if (rootI != rootJ) {
        dsuParent[rootI] = rootJ;
    }
}

// Hàm giải quyết bài toán với một nút gốc đã cho
LL calculateMaxScore(int rootNode) {
    std::memset(parentOfNode, 0, sizeof(parentOfNode));
    buildParentTree(rootNode, 0); // Xây dựng cây bắt đầu từ rootNode

    while (!groupQueue.empty()) groupQueue.pop(); // Xóa hàng đợi ưu tiên cũ

    // Khởi tạo DSU và thông tin cho mỗi nút như một nhóm riêng biệt
    for (int i = 1; i <= N_nodes; ++i) {
        dsuParent[i] = i; // Mỗi nút là cha của chính nó
        groupData[i] = { (LL)i, nodeValues[i], nodeValues[i], 1 }; // group_id, score, raw_sum, size
        groupQueue.push(groupData[i]); // Đẩy vào hàng đợi ưu tiên
    }

    // Quá trình hợp nhất tham lam
    while (!groupQueue.empty()) {
        GroupInfo currentGroup = groupQueue.top();
        groupQueue.pop();

        // Nếu thông tin nhóm trong hàng đợi đã lỗi thời (đã được hợp nhất hoặc thay đổi)
        // hoặc nếu nhóm hiện tại là nút gốc của cả cây (không thể hợp nhất lên cha)
        if (currentGroup != groupData[currentGroup.groupId] || currentGroup.groupId == rootNode) {
            continue;
        }

        LL parentOfCurrentGroupRepresentative = findSet(parentOfNode[currentGroup.groupId]);
        
        // Hợp nhất nhóm hiện tại vào nhóm cha của nó
        unionSets(currentGroup.groupId, parentOfCurrentGroupRepresentative);
        
        // Cập nhật thông tin cho nhóm cha mới
        groupData[parentOfCurrentGroupRepresentative].sumOfRawValues += currentGroup.sumOfRawValues;
        // Điểm tích lũy mới = điểm tích lũy cũ của cha + điểm tích lũy của nhóm con
        // + tổng giá trị gốc của nhóm con * kích thước của nhóm cha (vì các phần tử con sẽ bị đẩy lùi)
        groupData[parentOfCurrentGroupRepresentative].accumulatedScore += currentGroup.accumulatedScore + currentGroup.sumOfRawValues * groupData[parentOfCurrentGroupRepresentative].groupSize;
        groupData[parentOfCurrentGroupRepresentative].groupSize += currentGroup.groupSize;
        
        // Đẩy nhóm cha đã cập nhật vào hàng đợi ưu tiên
        groupQueue.push(groupData[parentOfCurrentGroupRepresentative]);
    }
    // Trả về tổng điểm tích lũy của nhóm gốc (đã chứa tất cả các nút con)
    return groupData[rootNode].accumulatedScore;
}

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

    std::cin >> N_nodes;
    for (int i = 1; i < N_nodes; ++i) {
        int u, v;
        std::cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    for (int i = 1; i <= N_nodes; ++i) {
        std::cin >> nodeValues[i] >> isRootCandidate[i];
    }

    LL overallMaxScore = 0;
    for (int i = 1; i <= N_nodes; ++i) {
        if (isRootCandidate[i]) {
            overallMaxScore = std::max(overallMaxScore, calculateMaxScore(i));
        }
    }
    std::cout << overallMaxScore << std::endl;

    return 0;
}

Vấn đề B: Tìm kiếm nhị phân cho bài toán đếm số lượng

Mức độ: Dễ đến Trung bình

Cho các số nguyên dương \(P\), \(Q\) và một số nguyên \(K\). Cần tìm số nguyên không âm nhỏ nhất \(M\) sao cho có ít nhất \(K\) số nguyên \(X\) trong khoảng \([0, M]\) thỏa mãn một điều kiện nhất định. Điều kiện cụ thể được suy ra từ công thức được sử dụng trong hàm kiểm tra của tìm kiếm nhị phân.

Ý tưởng chính:

• Trường hợp đặc biệt:

  • Nếu \(P < Q\): Không thể có giải pháp thỏa mãn điều kiện, in ra \(-1\).
  • Nếu \(P = Q\): Chỉ có giải pháp nếu \(K=1\), khi đó \(M=0\). Trong mọi trường hợp khác, in ra \(-1\).

• Trường hợp \(P > Q\): Sử dụng tìm kiếm nhị phân để tìm giá trị \(M\) nhỏ nhất thỏa mãn. Phạm vi tìm kiếm cho \(M\) có thể từ \(0\) đến một giá trị đủ lớn (ví dụ: \(2 \cdot 10^{15}\)).

• Hàm kiểm tra trong tìm kiếm nhị phân (\(countSatisfyingNumbers\)): Hàm này nhận vào một giá trị \(current\_M\) và đếm số lượng \(X\) trong \([0, current\_M]\) thỏa mãn điều kiện.

  • Công thức \(num\_distinct\_floor\_values = ((current\_M + 1) \cdot Q - 1) / P\) được dùng để tính số lượng các giá trị phân biệt của \(\lfloor X \cdot Q / P \rfloor\) khi \(X\) chạy từ \(0\) đến \(current\_M\). Đây là một cách tính \(\lceil (current\_M + 1) \cdot Q / P \rceil - 1\).
  • Số lượng các số \(X\) mà \(\lfloor X \cdot Q / P \rfloor\) không tạo ra một giá trị phân biệt mới (hoặc nói cách khác, trùng với một giá trị trước đó) là \((current\_M + 1) - num\_distinct\_floor\_values\). Bài toán yêu cầu tìm \(M\) nhỏ nhất sao cho có ít nhất \(K\) số \(X\) như vậy.
  • Nếu \((current\_M + 1) - num\_distinct\_floor\_values \geq K\), tức là có đủ số \(X\) thỏa mãn, ta có thể tìm \(M\) nhỏ hơn (đặt \(high\_bound = current\_M - 1\)). Ngược lại, cần \(M\) lớn hơn (đặt \(low\_bound = current\_M + 1\)).

Độ phức tạp:

\(O(\log(\text{MAX_M}))\), trong đó \(\text{MAX_M}\) là giới hạn trên của \(M\).

Mã nguồn C++:

#include <iostream>

#define LL long long

// Hàm kiểm tra điều kiện cho tìm kiếm nhị phân.
// Đếm số lượng giá trị 'x' trong khoảng [0, current_M] thỏa mãn tiêu chí:
// floor(x * val_Q / val_P) không phải là giá trị phân biệt mới so với các x' < x.
LL countSatisfyingNumbers(LL current_M, LL val_P, LL val_Q) {
    // num_distinct_floor_values tính số lượng các giá trị `floor(X * val_Q / val_P)` phân biệt
    // khi X chạy từ 0 đến current_M.
    // Công thức này tương đương với `ceil(((current_M + 1) * val_Q) / val_P) - 1`.
    LL num_distinct_floor_values = ((current_M + 1) * val_Q - 1) / val_P;
    
    // Số lượng các số X trong [0, current_M] mà floor(X * val_Q / val_P) 
    // không tạo ra một giá trị phân biệt mới.
    return (current_M + 1) - num_distinct_floor_values;
}


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

    LL testCases;
    std::cin >> testCases;
    while (testCases--) {
        LL val_P, val_Q, target_K;
        std::cin >> val_P >> val_Q >> target_K;

        if (val_P < val_Q) {
            std::cout << -1 << std::endl;
        } else if (val_P == val_Q) {
            if (target_K > 1) {
                std::cout << -1 << std::endl;
            } else { // target_K == 1
                std::cout << 0 << std::endl;
            }
        } else { // val_P > val_Q
            LL low_bound = 0, high_bound = 2e15; // Giới hạn trên đủ lớn
            LL result_M = high_bound; // Lưu kết quả M nhỏ nhất

            while (low_bound <= high_bound) {
                LL current_M = low_bound + (high_bound - low_bound) / 2;
                if (countSatisfyingNumbers(current_M, val_P, val_Q) >= target_K) {
                    result_M = current_M; // current_M là một ứng viên, thử tìm nhỏ hơn
                    high_bound = current_M - 1;
                } else {
                    low_bound = current_M + 1; // current_M quá nhỏ, cần M lớn hơn
                }
            } 
            std::cout << result_M << std::endl;
        }   
    }
    return 0;
}

Vấn đề C: Công thức tổ hợp và lũy thừa theo modulo

Mức độ: Dễ

Bài toán yêu cầu tính số cách sắp xếp hoặc lựa chọn tuân theo một công thức tổ hợp cụ thể, với kết quả theo modulo \(10^9 + 7\).

Ý tưởng chính:

• Công thức đã cho là \(((N - K)^{N - K}) \cdot (K^{K - 1})) \pmod{\text{MOD}}\).
• Sử dụng hàm lũy thừa theo modulo (modular exponentiation) để tính \(A^B \pmod M\) một cách hiệu quả trong thời gian \(O(\log B)\).
• Lưu ý các trường hợp đặc biệt:
  • Nếu \((N - K) = 0\) và số mũ cũng là \(0\) (ví dụ \(N=K\)), thì \(0^0\) được coi là \(1\) trong ngữ cảnh tổ hợp.
  • Tương tự, nếu \(K = 1\), thì \(K - 1 = 0\), do đó \(1^0\) được coi là \(1\).
  • Đảm bảo rằng các cơ số \((N - K)\) và \(K\) được lấy modulo \(\text{MOD}\) trước khi tính lũy thừa để tránh tràn số và đảm bảo kết quả đúng.

Độ phức tạp:

\(O(\log(N + K))\) do sử dụng thuật toán lũy thừa theo modulo.

Mã nguồn C++:

#include <iostream>

#define LL long long
#define MOD 1000000007 // Modulo cần tính

// Hàm tính lũy thừa theo modulo (modular exponentiation)
// Tính (base_val ^ exponent_val) % MOD
LL power_modulo(LL base_val, LL exponent_val) {
    LL result = 1;
    base_val %= MOD; // Đảm bảo cơ số nằm trong giới hạn modulo

    while (exponent_val > 0) {
        if (exponent_val % 2 == 1) { // Nếu số mũ lẻ, nhân kết quả với cơ số
            result = (result * base_val) % MOD;
        }
        base_val = (base_val * base_val) % MOD; // Bình phương cơ số
        exponent_val /= 2; // Chia đôi số mũ
    }
    return result;
}

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

    LL num_N, num_K;
    std::cin >> num_N >> num_K;

    // Tính thành phần thứ nhất: (num_N - num_K)^(num_N - num_K)
    LL base_first_term = num_N - num_K;
    LL exponent_first_term = num_N - num_K;
    LL first_term_result;
    if (base_first_term == 0 && exponent_first_term == 0) { // Xử lý trường hợp 0^0 = 1
        first_term_result = 1;
    } else {
        first_term_result = power_modulo(base_first_term, exponent_first_term);
    }
    
    // Tính thành phần thứ hai: num_K^(num_K - 1)
    LL base_second_term = num_K;
    LL exponent_second_term = num_K - 1;
    LL second_term_result;
    // Xử lý trường hợp 0^0 = 1 (khi num_K = 1, thì exponent_second_term = 0)
    // Hoặc trường hợp 0^(-1) nếu num_K = 0 (thường không xảy ra trong bài toán tổ hợp hợp lệ)
    if (base_second_term == 0 && exponent_second_term == 0) {
        second_term_result = 1; 
    } else if (exponent_second_term < 0) { // Nếu num_K = 0, thì exponent_second_term = -1.
                                        // Giả sử bài toán đảm bảo num_K >= 1.
                                        // Nếu không, cần xử lý cụ thể theo yêu cầu đề bài.
        second_term_result = 0; // Hoặc giá trị mặc định khác nếu K=0
    } else {
         second_term_result = power_modulo(base_second_term, exponent_second_term);
    }

    // Kết quả cuối cùng là tích của hai thành phần, lấy modulo
    LL total_ways = (first_term_result * second_term_result) % MOD;
    std::cout << total_ways << std::endl;

    return 0;
}

Vấn đề D: Quy hoạch động trạng thái với dãy con tăng dài nhất duy nhất

Mức độ: Khó

Bài toán yêu cầu đếm số lượng hoán vị \(S\) của các số từ \(1\) đến \(N\) sao cho một dãy con tăng dần \(A\) (độ dài \(K\)) cho trước là dãy con tăng dài nhất (LIS) duy nhất của \(S\). Điều này có nghĩa là không có LIS nào khác của \(S\) có độ dài \(K\), và không có LIS nào dài hơn \(K\).

Ý tưởng chính:

• Sử dụng kỹ thuật quy hoạch động (DP) với biểu diễn trạng thái nén (state compression) dựa trên hệ cơ số 3. Mỗi số \(j\) (từ \(0\) đến \(N-1\)) có thể ở một trong ba trạng thái trong mask của DP:
  • 0: Số \(j\) chưa xuất hiện trong hoán vị \(S\).
  • 1: Số \(j\) đã xuất hiện trong \(S\) VÀ nó là một phần của dãy con tăng dài nhất \(A\) đã cho.
  • 2: Số \(j\) đã xuất hiện trong \(S\) NHƯNG nó KHÔNG phải là một phần của dãy con tăng dài nhất \(A\) đã cho.
• dp_counts[mask]: Lưu trữ số lượng hoán vị con (tiền tố của \(S\)) mà trạng thái của các số được mã hóa bởi \(mask\).
• Mảng tiền xử lý is_insertable[binary_mask][j]:
  • binary_mask: Một mask nhị phân biểu diễn tập hợp các số đã có mặt trong phần hoán vị đã xây dựng.
  • j: Số đang xét để chèn vào hoán vị.
  • is_insertable[binary_mask][j] là true nếu số \(j\) có thể được chèn vào. Điều kiện là \(j\) chưa có trong binary_mask, VÀ tất cả các phần tử \(a_i\) (từ dãy \(A\)) đứng trước \(j\) trong dãy \(A\) đều đã có trong binary_mask. Điều này giúp đảm bảo rằng chúng ta đang xây dựng dãy \(A\) một cách tuần tự và hợp lệ.
• Chuyển đổi trạng thái:
  • Lặp qua tất cả các trạng thái \(current\_ternary\_mask\) hiện có trong DP.
  • Từ \(current\_ternary\_mask\), xác định current_binary_mask (tập hợp các số đã có trong \(S\)) và mảng elements_from_LIS_A (các giá trị của \(A\) hiện đang ở trạng thái 1).
  • Lặp qua các số \(j\) từ \(0\) đến \(N-1\) để thử chèn \(j\) vào hoán vị.
  • Nếu is_insertable[current_binary_mask][j] là false, bỏ qua \(j\).
  • Tìm vị trí \(current\_LIS\_idx\) trong elements_from_LIS_A (tương ứng với \(l\) trong code gốc) sao cho \(j\) có thể theo sau \(elements\_from\_LIS\_A[current\_LIS\_idx - 1]\) và trước \(elements\_from\_LIS\_A[current\_LIS\_idx]\) trong một dãy tăng.
  • Tính toán next_ternary_mask: Đây là phần phức tạp nhất. Nếu \(j\) được chèn vào:
    • Giả sử \(j\) được thêm vào như phần tử thứ \(l\) của LIS \(A\). Do đó, \(j\) chuyển từ trạng thái 0 sang trạng thái 1. (Thêm \(1 \cdot 3^j\) vào mask).
    • Phần tử \(ok[l]\) (tức là \(elements\_from\_LIS\_A[current\_LIS\_idx]\) trong code của chúng ta, là phần tử của \(A\) mà \(j\) "thay thế" hoặc "đẩy lùi") sẽ chuyển từ trạng thái 1 sang trạng thái 2. (Thêm \(1 \cdot 3^{ok[l]}\) vào mask, vì \(current\_mask\) đã có \(1 \cdot 3^{ok[l]}\), thêm \(1 \cdot 3^{ok[l]}\) nữa sẽ thành \(2 \cdot 3^{ok[l]}\)).
    • Vậy, \(next\_ternary\_mask = current\_ternary\_mask + power\_of\_3[elements\_from\_LIS\_A[current\_LIS\_idx]] + power\_of\_3[j]\).
    • Cộng dp_counts[current_ternary_mask] vào dp_counts[next_ternary_mask].
• Kết quả cuối cùng: Tổng dp_counts[mask] cho tất cả các \(mask\) mà current_binary_mask chứa tất cả các số từ \(0\) đến \(N-1\), VÀ số lượng các phần tử của \(A\) đã được xác định là trạng thái 1 (\(count\_in\_LIS\_A\)) bằng \(K\_len - 1\) (vì \(K\_len\) là độ dài LIS, và chỉ số 0-based).

Độ phức tạp:

\(O(3^N \cdot N^2)\), với \(N\) là số lượng số và \(K\) là độ dài LIS. \(3^N\) là số trạng thái, mỗi trạng thái có \(N\) lần lặp để chọn số chèn và \(O(N)\) để tìm vị trí \(l\).

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <numeric> 
#include <cstring> 
#include <algorithm> // For std::sort

#define LL long long
#define MAX_N 20 // N tối đa khoảng 16-19 vì 3^N sẽ rất lớn
#define MAX_TERNARY_MASK 1162261468 // 3^19 + buffer
#define MAX_BINARY_MASK (1 << MAX_N) // 2^N_val

LL N_val, K_len; // N_val: số lượng số, K_len: độ dài LIS A
int givenLIS_A[MAX_N]; // Dãy A, các giá trị được chuẩn hóa về 0..N-1
LL dp_counts[MAX_TERNARY_MASK]; // Mảng DP: dp_counts[mask] là số cách tạo tiền tố
LL power_of_3[MAX_N]; // Lưu 3^i
LL total_ternary_masks = 1; // Tổng số trạng thái 3-phân

// is_insertable[binary_mask][j]: true nếu số j có thể được chèn vào
// khi các số trong binary_mask đã có mặt trong permutation
bool is_insertable[MAX_BINARY_MASK][MAX_N];

// Hàm khởi tạo và đọc dữ liệu
void initialize() {
    std::cin >> N_val >> K_len;
    for (int i = 0; i < K_len; ++i) { // givenLIS_A lưu 0-indexed
        std::cin >> givenLIS_A[i];
        givenLIS_A[i]--; // Chuyển sang chỉ số 0-based
    }
    // Sắp xếp dãy A để dễ dàng tìm kiếm các phần tử trong LIS
    std::sort(givenLIS_A, givenLIS_A + K_len);

    power_of_3[0] = 1;
    for (int i = 1; i <= N_val; ++i) {
        power_of_3[i] = power_of_3[i - 1] * 3;
    }
    total_ternary_masks = power_of_3[N_val];

    // Tiền xử lý mảng is_insertable
    // `current_binary_mask` biểu diễn tập hợp các số đã có trong hoán vị (binary)
    for (int current_binary_mask = 0; current_binary_mask < (1 << N_val); ++current_binary_mask) {
        for (int j = 0; j < N_val; ++j) {
            // Nếu j đã có trong `current_binary_mask`, không thể chèn
            if ((current_binary_mask >> j) & 1) {
                is_insertable[current_binary_mask][j] = false;
                continue;
            }
            // Mặc định là có thể chèn nếu chưa có
            is_insertable[current_binary_mask][j] = true;

            int pos_in_LIS_A = -1; // Vị trí của j trong dãy A
            for(int l = 0; l < K_len; ++l) {
                if (givenLIS_A[l] == j) {
                    pos_in_LIS_A = l;
                    break;
                }
            }
            
            // Nếu j là một phần tử của LIS A, kiểm tra các phần tử trước đó
            if (pos_in_LIS_A != -1) {
                for (int l = 0; l < pos_in_LIS_A; ++l) {
                    // Nếu phần tử A[l] chưa có trong `current_binary_mask`
                    if (!((current_binary_mask >> givenLIS_A[l]) & 1)) {
                        is_insertable[current_binary_mask][j] = false; // Không thể chèn j
                        break;
                    }
                }
            }
        }
    }
}

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

    initialize();

    dp_counts[0] = 1; // Khởi tạo: có 1 cách để tạo hoán vị rỗng (mask 0)
    LL total_LIS_permutations = 0; // Tổng số hoán vị S thỏa mãn

    // Duyệt qua tất cả các trạng thái mask (ternary)
    for (LL current_ternary_mask = 0; current_ternary_mask < total_ternary_masks; ++current_ternary_mask) {
        if (!dp_counts[current_ternary_mask]) continue;

        LL current_binary_mask = 0; // Biểu diễn tập hợp các số đã có trong S
        int count_LIS_elements_in_S = 0; // Số lượng các phần tử của A đã có trong S (trạng thái 1)
        
        // Mảng lưu trữ các giá trị của A đã có trong S và đang ở trạng thái 1, theo thứ tự tăng dần
        std::vector<int> elements_from_LIS_A_in_state1;

        LL temp_mask_for_state_extraction = current_ternary_mask;
        for (int j = 0; j < N_val; ++j) {
            int state_of_j = temp_mask_for_state_extraction % 3;
            if (state_of_j != 0) { // Nếu j đã có trong hoán vị S
                current_binary_mask |= (1 << j);
                if (state_of_j == 1) { // Nếu j cũng là phần tử của LIS A
                    elements_from_LIS_A_in_state1.push_back(j);
                    count_LIS_elements_in_S++;
                }
            }
            temp_mask_for_state_extraction /= 3;
        }

        // Nếu số lượng phần tử của A đã có trong S vượt quá K_len, bỏ qua
        if (count_LIS_elements_in_S > K_len) continue;
        
        // Thêm giá trị sentinel để đơn giản hóa tìm kiếm
        elements_from_LIS_A_in_state1.push_back(N_val + 1); 

        // Thử chèn các số chưa có vào hoán vị
        int current_LIS_vector_idx = 0; // Chỉ số vào elements_from_LIS_A_in_state1
        for (int j = 0; j < N_val; ++j) {
            // Nếu j không thể chèn vào theo điều kiện LIS A
            if (!is_insertable[current_binary_mask][j]) continue;

            // current_LIS_vector_idx sẽ trỏ đến phần tử đầu tiên trong elements_from_LIS_A_in_state1
            // mà j không lớn hơn nó. (Đây là 'l' trong code gốc)
            while (current_LIS_vector_idx < elements_from_LIS_A_in_state1.size() - 1 && 
                   j > elements_from_LIS_A_in_state1[current_LIS_vector_idx]) {
                current_LIS_vector_idx++;
            }

            // Tính toán next_ternary_mask
            LL next_ternary_mask = current_ternary_mask;
            
            // Xảy ra chuyển trạng thái:
            // elements_from_LIS_A_in_state1[current_LIS_vector_idx] (tức là ok[l] trong code gốc)
            // chuyển từ trạng thái 1 (trong S và trong A) sang trạng thái 2 (trong S nhưng không trong A).
            // Điều này được thực hiện bằng cách thêm power_of_3[value] * 1 vào mask hiện có.
            // (Vì nó đã có 1 * power_of_3[value], thêm 1 nữa thành 2 * power_of_3[value]).
            next_ternary_mask += power_of_3[elements_from_LIS_A_in_state1[current_LIS_vector_idx]];
            
            // j (giá trị mới được chèn) chuyển từ trạng thái 0 (chưa trong S) sang trạng thái 1 (trong S và trong A).
            // Điều này được thực hiện bằng cách thêm power_of_3[j] * 1 vào mask.
            next_ternary_mask += power_of_3[j];

            // Cập nhật giá trị DP
            dp_counts[next_ternary_mask] += dp_counts[current_ternary_mask];
        }

        // Nếu tất cả N_val số đã được chèn vào hoán vị (binary_mask đủ N bit)
        // VÀ số lượng phần tử của LIS A (trạng thái 1) bằng K_len
        if (current_binary_mask == (1 << N_val) - 1 && count_LIS_elements_in_S == K_len) {
            total_LIS_permutations += dp_counts[current_ternary_mask];
        }
    }
    std::cout << total_LIS_permutations << std::endl;

    return 0;
}