VOJ - C11BC1

Source: C11BC1
Tags: Dynamic Programming

Problem:
Một đất nước có N thành phố, mỗi thành phố được đặc trưng bởi 2 chỉ số A[i] và B[i], trong đó A[i] thể hiện khả năng tăng trưởng của thành phố đó và B[i] thể hiện chỉ số ngôn ngữ của thành phố đó. Một "liên minh" là một tập hợp gồm K thành phố trong N thành phố trong đó có ít nhất 2 thành phố khác nhau về chỉ số ngôn ngữ. Khả năng liên minh của một liên minh K thành phố là tích các chỉ số tăng trưởng của K thành phố đó. Khả năng tăng trưởng của một đất nước sẽ được tính bằng tổng tất cả khả năng liên minh của các liên minh khác nhau. Hai liên minh được coi là khác nhau nếu có ít nhất một thành phố thuộc liên minh này nhưng không thuộc liên minh kia.
2 ≤ N ≤ 1e5.
2 ≤ K ≤ 50.
A[i] ≤ 1e3.
B[i] ≤ 1e9.
In ra khả năng tăng trưởng của đất nước theo module 790972.

Ví dụ:
Input:
5 3
4 1
6 4
5 3
2 2
3 5

Output:
580

Explanation:
Các thành phố đều có chỉ số ngôn ngữ khác nhau nên đáp án là tổng các tích 3 thành phố bất kỳ.

Solution:
Mình sử dụng phương pháp bao hàm - loại trừ (Inclusion - Exclusion Principle) để giải bài này. Tức là, đi tính tổng tất cả bộ K thành phố rồi trừ đi những bộ K không phải là một liên minh, nói cách khác là những bộ K có cùng chỉ số ngôn ngữ.
Đầu tiên ta sort các thành phố lại theo chỉ số ngôn ngữ, sau đó tìm đoạn các thành phố có cùng ngôn ngữ rồi tiến hành tính tổng các tích để trừ đi. Vậy giờ điều khó khăn là tính tổng các tích này như thế nào? Chắc chắn không phải là sinh nhị phân ra tính rồi. Giả sử ta muốn tính tổng các tích của j thành phố trong đó có thành phố i, ta đã chắc chắn là có thành phố i các tích đó nên ta có thể đặt A[i] ra làm thừa số chung, vậy giờ điều ta cần tính chính là tổng các tích của j - 1 thành phố trước đó. Do đó ta có công thức như sau, gọi F[i][j] là tổng các tích của j thành phố tính từ thành phố 1 đến thành phố i: F[i][j] = F[i - 1][j - 1] * A[i] + F[i - 1][j].
Sau khi đã thấm nhuần công thức trên, ta sử dụng công thức này cho dãy N thành phố ban đầu để tính tổng tất cả bộ K thành phố trong N thành phố, sau đó ta có thể tách các đoạn gồm các thành phố cùng chỉ số ngôn ngữ thành các dãy số riêng biệt và áp dụng công thức này cho từng dãy, rồi lấy tổng trừ đi đáp án từng dãy, kết quả cuối cùng là khả năng tăng trưởng của đất nước cần tìm.
Độ phức tạp O(2NK)

Code:
#include <iostream>
#include <algorithm>

using namespace std;

const int MOD = 790972;
int n, k;
pair <int, int> city[100015];
long long dp[100015][55], res;

long long calc(int l, int r) {
    for (int i = l - 1; i <= r; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = j == 0;
    for (int i = l; i <= r; i++)
        for (int j = 1; j <= k; j++)
            dp[i][j] = (dp[i - 1][j - 1] * city[i].second + dp[i - 1][j]) % MOD;
    return dp[r][k];
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> city[i].second >> city[i].first;
    sort(city + 1, city + n + 1);
    res = calc(1, n);
    for (int i = 1, j; i <= n; i = j) {
        for (j = i + 1; j <= n && city[i].first == city[j].first; j++);
        if (j - i >= k) res = (res - calc(i, j - 1) + MOD) % MOD;
    }
    cout << res;

}