Editorial for Chọn người quanh vòng tròn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Nhìn vào khoảng trống giữa người được chọn

Nếu chọn K người, hãy đi quanh vòng tròn và đếm số người không được chọn nằm giữa mỗi cặp người được chọn liên tiếp. Mỗi khoảng trống phải có ít nhất một người.

Gợi ý 2 - Đếm các cách chia khoảng trống

Đánh dấu một người được chọn làm điểm bắt đầu. Có N lựa chọn cho người này. Phân phối N-K người còn lại vào K khoảng trống, mỗi khoảng ít nhất một người, có C(N-K-1, K-1) cách. Mỗi tập hợp bị đếm K lần vì có thể đánh dấu bất kỳ người nào trong K người đã chọn.

Lời giải đầy đủ

Công thức

Với K = 0, chỉ có một tập rỗng. Nếu 2K > N thì không thể chọn đủ K người mà không có hai người kề nhau.

Với K > 0 và 2K <= N, kết quả là N / K * C(N-K-1, K-1), lấy modulo 1000000007. Vì K <= 200000 nên ta tính tổ hợp bằng tích các tử số và nghịch đảo modulo của các mẫu số từ 1 đến K-1.

Độ phức tạp

Tiền xử lý nghịch đảo và tính tích mất O(K) thời gian, bộ nhớ O(K).

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

const long long MOD = 1'000'000'007;

long long modPow(long long a, long long e) {
    long long result = 1;
    while (e > 0) {
        if (e & 1) result = result * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return result;
}

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

    long long n;
    int k;
    cin >> n >> k;

    if (k == 0) {
        cout << 1 << endl;
        return 0;
    }
    if (2LL * k > n) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> inverse(k + 1, 0);
    inverse[1] = 1;
    for (int i = 2; i <= k; ++i) {
        inverse[i] = MOD - (MOD / i) * inverse[MOD % i] % MOD;
    }

    long long choose = 1;
    for (int i = 1; i < k; ++i) {
        long long numerator = (n - k - i) % MOD;
        choose = choose * numerator % MOD * inverse[i] % MOD;
    }

    long long answer = (n % MOD) * inverse[k] % MOD * choose % MOD;
    cout << answer << endl;
    return 0;
}

Loading...