Cầm cờ (Đề tự luyện HSG Tin quốc gia – Bài 1)

Nguồn: Đề tự luyện HSG Tin học quốc gia – Bài 1 (đề tự soạn)Độ khó: KháTổ hợpĐếm đóng gópĐẳng thức VandermondeĐếm phần bùNghịch đảo modulo

Đề bài

Cầm cờ

Lớp của thầy Sơn có $N$ học sinh, bạn thứ $i$ cao $h_i$. Mỗi tập con khác rỗng các bạn là một đội cờ. Đội xếp hàng theo chiều cao không giảm; đội có $k$ bạn thì: $k$ lẻ – bạn đứng thứ $\frac{k+1}{2}$ cầm cờ; $k$ chẵn – hai bạn đứng thứ $\frac{k}{2}$ và $\frac{k}{2}+1$ cùng cầm cờ. Độ cao của đội là tổng chiều cao (các) bạn cầm cờ.

Với mỗi bạn $p$, tính $G_p$ = tổng độ cao của tất cả $2^{N-1}$ đội có bạn $p$ tham gia, modulo $10^9+7$.

Dữ liệu vào: dòng đầu $N$ $(1 \le N \le 2\cdot 10^5)$; dòng sau $h_1, \ldots, h_N$ $(1 \le h_i \le 10^9)$.

Kết quả: $N$ dòng, dòng thứ $p$ là $G_p \bmod (10^9+7)$.

Subtask 1 (20%): $N \le 15$.
Subtask 2 (30%): $N \le 5000$.
Subtask 3 (15%): mọi $h_i$ bằng nhau.
Subtask 4 (35%): không có ràng buộc gì thêm.

Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.

Input

3
150 170 160

Output

940
980
960

Giải thích

Các đội có bạn 1: $\{1\}$ độ cao $150$; $\{1,2\}$ độ cao $150+170=320$; $\{1,3\}$ độ cao $310$; $\{1,2,3\}$ xếp $150, 160, 170$, bạn 3 cầm cờ, độ cao $160$. Vậy $G_1 = 940$.

Input

4
160 150 170 150

Output

Giải thích

Đội $\{1,2,4\}$ xếp $150, 150, 160$, người giữa cao $150$; đội $\{1,2,3,4\}$ xếp $150, 150, 160, 170$, độ cao $150+160 = 310$. Bạn 2 và bạn 4 cao bằng nhau nên $G_2 = G_4$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Cầm cờ

Lời mở đầu

Mỗi bạn góp mặt trong $2^{N-1}$ đội, với $N = 2\cdot 10^5$ thì không thể duyệt từng đội. Bài này là một bài "đếm" điển hình của đề chọn đội tuyển: code rất ngắn, nhưng phải có ba nhận xét đi liền nhau.

Đổi góc nhìn – đếm đóng góp. Thay vì đi qua từng đội rồi xem ai cầm cờ, ta hỏi ngược lại: mỗi bạn được cầm cờ trong bao nhiêu đội? Nếu bạn đó cầm cờ trong $W$ đội thì bạn đó đóng góp $h \cdot W$ vào tổng.
Sắp xếp. Sau khi sắp chiều cao tăng dần $s_1 \le s_2 \le \ldots \le s_N$ (cao bằng nhau thì xếp theo chỉ số), "đứng thứ mấy trong đội" chỉ phụ thuộc vào việc đội lấy bao nhiêu bạn bên trái và bao nhiêu bạn bên phải của mình trong dãy đã sắp. Các bạn cao bằng nhau không gây rắc rối: đổi chỗ họ thì độ cao của đội không đổi.
Phần bù. "Tổng trên các đội có bạn $p$" $=$ "tổng trên mọi đội" $-$ "tổng trên các đội không có bạn $p$". Mà các đội không có $p$ chính là mọi đội của một lớp chỉ có $N-1$ bạn!

Đứng thứ mấy trong đội chỉ phụ thuộc vào số bạn được chọn ở hai bên.

Lộ trình:

Cách 1Duyệt mọi đội · 20%Cách 2Đếm đóng góp + phần bù · 50%Cách 3Mọi bạn cao bằng nhau · 65%Cách 4Đẳng thức Vandermonde · 100%

Cách 1Duyệt mọi đội – O(2^N · N log N) · 20%

Với $N \le 15$ chỉ có $2^{15} - 1 = 32767$ đội. Mỗi đội là một số nhị phân mask: lấy chiều cao các bạn trong đội, sắp xếp, tính độ cao đội rồi cộng vào $G_p$ của mọi bạn $p$ có trong đội. Lưu ý độ cao đội chẵn là tổng hai số tới $10^9$, vượt int – nhớ dùng long long.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int main() {
    int n;
    scanf("%d", &n);
    vector<ll> h(n);
    for (auto &x : h) scanf("%lld", &x);
    vector<ll> ans(n, 0);
    for (int mask = 1; mask < (1 << n); mask++) {     // moi doi = mot tap con khac rong
        vector<ll> v;
        for (int i = 0; i < n; i++) if (mask >> i & 1) v.push_back(h[i]);
        sort(v.begin(), v.end());
        int k = v.size();
        ll val = (k % 2 == 1) ? v[k / 2] : v[k / 2 - 1] + v[k / 2];   // tong chieu cao nguoi cam co
        for (int i = 0; i < n; i++) if (mask >> i & 1) ans[i] = (ans[i] + val) % MOD;
    }
    for (int i = 0; i < n; i++) printf("%lld\n", ans[i]);
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 10**9 + 7
    n = int(data[0])
    h = list(map(int, data[1:n + 1]))
    ans = [0] * n
    for mask in range(1, 1 << n):          # moi doi = mot tap con khac rong
        v = sorted(h[i] for i in range(n) if mask >> i & 1)
        k = len(v)
        val = v[k // 2] if k % 2 == 1 else v[k // 2 - 1] + v[k // 2]
        for i in range(n):
            if mask >> i & 1:
                ans[i] += val
    sys.stdout.write("\n".join(str(x % MOD) for x in ans) + "\n")

main()

Không gian$O(N)$

Thời gian$O(2^N \cdot N \log N)$

Cách 2Đếm đóng góp + phần bù – O(N²) · 50%

Bước 1 – tổng trên mọi đội. Sắp xếp $s_1 \le \ldots \le s_N$. Xét bạn ở vị trí $j$, bên trái có $a = j - 1$ bạn, bên phải có $b = N - j$ bạn. Theo hình ở trên, số lần bạn này cầm cờ là

$$W_N(j) = \sum_{t \ge 0} \binom{a}{t}\binom{b}{t} \;+\; \sum_{t \ge 1} \binom{a}{t-1}\binom{b}{t} \;+\; \sum_{t \ge 1} \binom{a}{t}\binom{b}{t-1}.$$

Ba tổng lần lượt là: đội lẻ (đứng chính giữa), đội chẵn (đứng thứ $t$ – nửa dưới), đội chẵn (đứng thứ $t+1$ – nửa trên). Tổng độ cao của mọi đội là $F_N = \sum_j s_j \cdot W_N(j)$.

Ví dụ 1: dãy đã sắp $150, 160, 170$ có $W_3 = (3, 4, 3)$, nên $F_3 = 150\cdot 3 + 160 \cdot 4 + 170 \cdot 3 = 1600$ – đúng bằng tổng độ cao của cả 7 đội ($150+170+160+320+310+330+160$).

Bước 2 – phần bù. Bỏ bạn $p$ (đang đứng ở vị trí $r$ trong dãy đã sắp) ra khỏi lớp, ta được một lớp $N-1$ bạn: những bạn ở vị trí $j < r$ vẫn đứng ở vị trí $j$, những bạn ở vị trí $j > r$ lùi lên vị trí $j - 1$. Do đó

$$G_p = F_N - \Big(\sum_{j < r} s_j \cdot W_{N-1}(j) + \sum_{j > r} s_j \cdot W_{N-1}(j-1)\Big).$$

Ví dụ 1, bạn $p = 1$ (cao 150, vị trí $r=1$): lớp còn $160, 170$ với $W_2 = (2, 2)$, tổng $= 660$, nên $G_1 = 1600 - 660 = 940$. Chính xác!

Đừng quên "lùi vị trí"

Nếu dùng nhầm $W_{N-1}(j)$ cho cả các bạn đứng sau $p$ thì sai ngay (lời giải wrong_noshift.cpp chỉ đúng 2 test nhỏ). Và vì lấy hiệu theo modulo, kết quả có thể âm trong C++: phải cộng thêm MOD trước khi lấy dư.

Mô phỏng dưới đây chạy đúng hai bước trên (số nhỏ nên không cần lấy modulo):

Chiều cao h

Ví dụ nhanh:

Tính $W_N$ và $W_{N-1}$ mất $O(N^2)$ (mỗi vị trí một vòng lặp theo $t$), mỗi bạn $p$ thêm $O(N)$ để tính phần bù: tổng cộng $O(N^2)$, đủ cho $N \le 5000$. Hệ số tổ hợp tính bằng giai thừa và nghịch đảo modulo (định lý Fermat nhỏ).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
vector<ll> f, fi;
ll C(int a, int b) {
    if (a < 0 || b < 0 || b > a) return 0;
    return f[a] * fi[b] % MOD * fi[a - b] % MOD;
}
ll pw(ll a, ll e) { ll r = 1; for (; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }
// W[j]: so lan nguoi dung thu j (trong m nguoi) cam co, tinh truc tiep theo t
vector<ll> calcW(int m) {
    vector<ll> W(m + 2, 0);
    for (int j = 1; j <= m; j++) {
        int a = j - 1, b = m - j;              // a nguoi thap hon, b nguoi cao hon
        ll w = 0;
        for (int t = 0; t <= min(a, b); t++) w += C(a, t) * C(b, t) % MOD;          // doi le 2t+1
        for (int t = 1; t <= min(a + 1, b); t++) w += C(a, t - 1) * C(b, t) % MOD;  // dung thu t / 2t
        for (int t = 1; t <= min(a, b + 1); t++) w += C(a, t) * C(b, t - 1) % MOD;  // dung thu t+1 / 2t
        W[j] = w % MOD;
    }
    return W;
}
int main() {
    int n;
    scanf("%d", &n);
    vector<ll> h(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    f.assign(n + 1, 1); fi.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
    fi[n] = pw(f[n], MOD - 2);
    for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
    vector<int> id(n);
    iota(id.begin(), id.end(), 1);
    sort(id.begin(), id.end(), [&](int x, int y) { return h[x] < h[y]; });
    vector<ll> s(n + 2, 0);
    vector<int> rk(n + 1);
    for (int j = 1; j <= n; j++) { s[j] = h[id[j - 1]]; rk[id[j - 1]] = j; }
    vector<ll> W1 = calcW(n), W0 = calcW(n - 1);
    ll F = 0;
    for (int j = 1; j <= n; j++) F = (F + s[j] * W1[j]) % MOD;
    for (int p = 1; p <= n; p++) {
        int r = rk[p];
        ll G = 0;                              // tong tren cac doi KHONG co p
        for (int j = 1; j <= n; j++) {
            if (j < r) G = (G + s[j] * W0[j]) % MOD;
            if (j > r) G = (G + s[j] * W0[j - 1]) % MOD;
        }
        printf("%lld\n", ((F - G) % MOD + MOD) % MOD);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 10**9 + 7
    n = int(data[0])
    h = list(map(int, data[1:n + 1]))
    f = [1] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i - 1] * i % MOD
    fi = [1] * (n + 1)
    fi[n] = pow(f[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        fi[i - 1] = fi[i] * i % MOD

    def calcW(m):
        # W[j]: so lan nguoi dung thu j (trong m nguoi) cam co, tinh truc tiep theo t
        W = [0] * (m + 2)
        for j in range(1, m + 1):
            a = j - 1; b = m - j               # a nguoi thap hon, b nguoi cao hon
            k = min(a, b) + 1
            A = [f[a] * fi[t] % MOD * fi[a - t] % MOD for t in range(min(a, k) + 1)]   # A[t] = C(a, t)
            Bc = [f[b] * fi[t] % MOD * fi[b - t] % MOD for t in range(min(b, k) + 1)]  # Bc[t] = C(b, t)
            w = sum(x * y for x, y in zip(A, Bc))             # doi le 2t+1
            w += sum(x * y for x, y in zip(A, Bc[1:]))        # dung thu t trong doi 2t
            w += sum(x * y for x, y in zip(A[1:], Bc))        # dung thu t+1 trong doi 2t
            W[j] = w % MOD
        return W

    idx = sorted(range(n), key=h.__getitem__)
    s = [0] * (n + 2)
    rk = [0] * n
    for j in range(1, n + 1):
        s[j] = h[idx[j - 1]]
        rk[idx[j - 1]] = j
    W1 = calcW(n); W0 = calcW(n - 1)
    F = 0
    for j in range(1, n + 1):
        F = (F + s[j] * W1[j]) % MOD
    out = []
    for p in range(n):
        r = rk[p]
        G = 0                              # tong tren cac doi KHONG co p
        for j in range(1, r):
            G += s[j] * W0[j]
        for j in range(r + 1, n + 1):
            G += s[j] * W0[j - 1]
        out.append((F - G) % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 3Khi mọi bạn cao bằng nhau – O(N) · 65%

Nếu mọi bạn cùng cao $h$ thì độ cao một đội chỉ phụ thuộc vào số người cầm cờ: $h$ nếu đội lẻ, $2h$ nếu đội chẵn. Một lớp $m$ bạn có $2^{m-1}$ đội lẻ và $2^{m-1} - 1$ đội chẵn (khác rỗng), nên tổng số "lượt cầm cờ" là

$$H(m) = 2^{m-1} + 2\,(2^{m-1} - 1) = 3 \cdot 2^{m-1} - 2.$$

Lại dùng phần bù: số lượt cầm cờ trong các đội có bạn $p$ là $H(N) - H(N-1) = 3 \cdot 2^{N-2}$ (với $N \ge 2$; còn $N = 1$ thì bằng $1$). Vậy mọi $G_p = h \cdot 3 \cdot 2^{N-2}$. Kiểm tra với $N = 3$: $H(3) = 10$, $H(2) = 4$, hiệu $= 6 = 3 \cdot 2$ – đúng là bạn $p$ góp mặt trong 4 đội với $1 + 2 + 2 + 1 = 6$ lượt cầm cờ.

Code ghép Cách 2 với trường hợp đặc biệt này:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
vector<ll> f, fi;
ll C(int a, int b) {
    if (a < 0 || b < 0 || b > a) return 0;
    return f[a] * fi[b] % MOD * fi[a - b] % MOD;
}
ll pw(ll a, ll e) { ll r = 1; for (; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }
// W[j]: so lan nguoi dung thu j (trong m nguoi) cam co, tinh truc tiep theo t
vector<ll> calcW(int m) {
    vector<ll> W(m + 2, 0);
    for (int j = 1; j <= m; j++) {
        int a = j - 1, b = m - j;              // a nguoi thap hon, b nguoi cao hon
        ll w = 0;
        for (int t = 0; t <= min(a, b); t++) w += C(a, t) * C(b, t) % MOD;          // doi le 2t+1
        for (int t = 1; t <= min(a + 1, b); t++) w += C(a, t - 1) * C(b, t) % MOD;  // dung thu t / 2t
        for (int t = 1; t <= min(a, b + 1); t++) w += C(a, t) * C(b, t - 1) % MOD;  // dung thu t+1 / 2t
        W[j] = w % MOD;
    }
    return W;
}
int main() {
    int n;
    scanf("%d", &n);
    vector<ll> h(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    bool same = true;
    for (int i = 2; i <= n; i++) if (h[i] != h[1]) same = false;
    if (same) {                                // moi ban cao bang nhau
        ll cnt = (n == 1) ? 1 : 3 * pw(2, n - 2) % MOD;   // tong so luot cam co tren cac doi co p
        ll ans = h[1] % MOD * cnt % MOD;
        for (int p = 1; p <= n; p++) printf("%lld\n", ans);
        return 0;
    }
    f.assign(n + 1, 1); fi.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
    fi[n] = pw(f[n], MOD - 2);
    for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
    vector<int> id(n);
    iota(id.begin(), id.end(), 1);
    sort(id.begin(), id.end(), [&](int x, int y) { return h[x] < h[y]; });
    vector<ll> s(n + 2, 0);
    vector<int> rk(n + 1);
    for (int j = 1; j <= n; j++) { s[j] = h[id[j - 1]]; rk[id[j - 1]] = j; }
    vector<ll> W1 = calcW(n), W0 = calcW(n - 1);
    ll F = 0;
    for (int j = 1; j <= n; j++) F = (F + s[j] * W1[j]) % MOD;
    for (int p = 1; p <= n; p++) {
        int r = rk[p];
        ll G = 0;                              // tong tren cac doi KHONG co p
        for (int j = 1; j <= n; j++) {
            if (j < r) G = (G + s[j] * W0[j]) % MOD;
            if (j > r) G = (G + s[j] * W0[j - 1]) % MOD;
        }
        printf("%lld\n", ((F - G) % MOD + MOD) % MOD);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 10**9 + 7
    n = int(data[0])
    h = list(map(int, data[1:n + 1]))
    if min(h) == max(h):                   # moi ban cao bang nhau
        cnt = 1 if n == 1 else 3 * pow(2, n - 2, MOD) % MOD   # tong so luot cam co tren cac doi co p
        ans = h[0] * cnt % MOD
        sys.stdout.write((str(ans) + "\n") * n)
        return
    f = [1] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i - 1] * i % MOD
    fi = [1] * (n + 1)
    fi[n] = pow(f[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        fi[i - 1] = fi[i] * i % MOD

    def calcW(m):
        # W[j]: so lan nguoi dung thu j (trong m nguoi) cam co, tinh truc tiep theo t
        W = [0] * (m + 2)
        for j in range(1, m + 1):
            a = j - 1; b = m - j               # a nguoi thap hon, b nguoi cao hon
            k = min(a, b) + 1
            A = [f[a] * fi[t] % MOD * fi[a - t] % MOD for t in range(min(a, k) + 1)]   # A[t] = C(a, t)
            Bc = [f[b] * fi[t] % MOD * fi[b - t] % MOD for t in range(min(b, k) + 1)]  # Bc[t] = C(b, t)
            w = sum(x * y for x, y in zip(A, Bc))             # doi le 2t+1
            w += sum(x * y for x, y in zip(A, Bc[1:]))        # dung thu t trong doi 2t
            w += sum(x * y for x, y in zip(A[1:], Bc))        # dung thu t+1 trong doi 2t
            W[j] = w % MOD
        return W

    idx = sorted(range(n), key=h.__getitem__)
    s = [0] * (n + 2)
    rk = [0] * n
    for j in range(1, n + 1):
        s[j] = h[idx[j - 1]]
        rk[idx[j - 1]] = j
    W1 = calcW(n); W0 = calcW(n - 1)
    F = 0
    for j in range(1, n + 1):
        F = (F + s[j] * W1[j]) % MOD
    out = []
    for p in range(n):
        r = rk[p]
        G = 0                              # tong tren cac doi KHONG co p
        for j in range(1, r):
            G += s[j] * W0[j]
        for j in range(r + 1, n + 1):
            G += s[j] * W0[j - 1]
        out.append((F - G) % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N)$ khi mọi $h_i$ bằng nhau, $O(N^2)$ trong trường hợp còn lại

Một gợi ý nhỏ cho cách cuối

Ở Cách 3, tổng $\sum_j W_N(j) = 3\cdot 2^{N-1} - 2$ rút gọn được rất đẹp. Liệu từng $W_N(j)$ có rút gọn được không? Câu trả lời là có.

Cách 4Đẳng thức Vandermonde – O(N log N) · 100%

Nút thắt nằm ở tổng $\sum_t \binom{a}{t}\binom{b}{t}$. Viết $\binom{a}{t} = \binom{a}{a-t}$, ta có $\sum_t \binom{a}{a-t}\binom{b}{t}$: chọn $a - t$ người từ nhóm trái và $t$ người từ nhóm phải, tổng cộng luôn là $a$ người trong $a + b$ người. Vậy

$$\sum_{t} \binom{a}{t}\binom{b}{t} = \binom{a+b}{a}.$$

Song ánh "đổi phe bên trái"

Một đội lẻ có bạn $j$ đứng giữa ứng với: $t$ bạn được chọn bên trái, $t$ bạn được chọn bên phải. Lấy tập $X$ = (các bạn bên trái không được chọn) $\cup$ (các bạn bên phải được chọn). Khi đó $|X| = (a - t) + t = a$ luôn luôn, và từ $X$ ta khôi phục ngược lại được đội. Nên số đội lẻ mà bạn $j$ đứng giữa đúng bằng số cách chọn $a$ người trong $a + b = N - 1$ người còn lại.

Hai tổng còn lại làm y hệt: $\sum_t \binom{a}{t-1}\binom{b}{t} = \sum_t \binom{a}{a-t+1}\binom{b}{t} = \binom{a+b}{a+1}$ và $\sum_t \binom{a}{t}\binom{b}{t-1} = \binom{a+b}{a-1}$. Thay $a = j-1$, $a + b = N - 1$:

$$W_N(j) = \binom{N-1}{j-2} + \binom{N-1}{j-1} + \binom{N-1}{j}.$$

Kiểm tra: $W_3 = (0+1+2,\ 1+2+1,\ 2+1+0) = (3, 4, 3)$. Khớp với Cách 2!

a (bên trái) b (bên phải)

Ví dụ nhanh:

Bây giờ mỗi $W$ tính trong $O(1)$ bằng bảng giai thừa. Phần bù cũng không cần $O(N)$ cho mỗi bạn nữa: dùng hai mảng cộng dồn

$$L[j] = \sum_{i \le j} s_i \cdot W_{N-1}(i), \qquad R[j] = \sum_{i \ge j} s_i \cdot W_{N-1}(i - 1),$$

thì $G_p = F_N - L[r-1] - R[r+1]$ với $r$ là vị trí của bạn $p$ trong dãy đã sắp. Phần tốn nhất là sắp xếp: $O(N \log N)$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int n;
vector<ll> f, fi;
ll C(int a, int b) {
    if (a < 0 || b < 0 || b > a) return 0;
    return f[a] * fi[b] % MOD * fi[a - b] % MOD;
}
// W(m, j): so lan nguoi dung thu j (trong m nguoi) cam co
ll W(int m, int j) { return (C(m - 1, j - 2) + C(m - 1, j - 1) + C(m - 1, j)) % MOD; }
ll pw(ll a, ll e) { ll r = 1; a %= MOD; for (; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }
int main() {
    scanf("%d", &n);
    vector<ll> h(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    f.assign(n + 1, 1); fi.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
    fi[n] = pw(f[n], MOD - 2);
    for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
    vector<int> id(n);
    iota(id.begin(), id.end(), 1);
    sort(id.begin(), id.end(), [&](int x, int y) { return h[x] < h[y]; });
    vector<ll> s(n + 2, 0);
    vector<int> rk(n + 1);
    for (int j = 1; j <= n; j++) { s[j] = h[id[j - 1]]; rk[id[j - 1]] = j; }
    ll F = 0;                                  // tong tren moi doi
    for (int j = 1; j <= n; j++) F = (F + s[j] % MOD * W(n, j)) % MOD;
    vector<ll> L(n + 2, 0), R(n + 2, 0);       // tong khi bo bot 1 nguoi
    for (int j = 1; j <= n; j++) L[j] = (L[j - 1] + s[j] % MOD * W(n - 1, j)) % MOD;
    for (int j = n; j >= 1; j--) R[j] = (R[j + 1] + s[j] % MOD * W(n - 1, j - 1)) % MOD;
    for (int p = 1; p <= n; p++) {
        int r = rk[p];
        ll ans = ((F - L[r - 1] - R[r + 1]) % MOD + 2 * MOD) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    MOD = 10**9 + 7
    n = int(data[0])
    h = list(map(int, data[1:n + 1]))
    f = [1] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i - 1] * i % MOD
    fi = [1] * (n + 1)
    fi[n] = pow(f[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        fi[i - 1] = fi[i] * i % MOD

    def C(a, b):
        if a < 0 or b < 0 or b > a:
            return 0
        return f[a] * fi[b] % MOD * fi[a - b] % MOD

    def W(m, j):   # so lan nguoi dung thu j (trong m nguoi) cam co
        return (C(m - 1, j - 2) + C(m - 1, j - 1) + C(m - 1, j)) % MOD

    idx = sorted(range(n), key=h.__getitem__)
    s = [0] * (n + 2)
    rk = [0] * n
    for j in range(1, n + 1):
        s[j] = h[idx[j - 1]]
        rk[idx[j - 1]] = j
    F = 0                                   # tong tren moi doi
    for j in range(1, n + 1):
        F = (F + s[j] * W(n, j)) % MOD
    L = [0] * (n + 2)                       # tong khi bo bot 1 nguoi
    R = [0] * (n + 2)
    for j in range(1, n + 1):
        L[j] = (L[j - 1] + s[j] * W(n - 1, j)) % MOD
    for j in range(n, 0, -1):
        R[j] = (R[j + 1] + s[j] * W(n - 1, j - 1)) % MOD
    out = []
    for p in range(n):
        r = rk[p]
        out.append((F - L[r - 1] - R[r + 1]) % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N \log N)$

C++▶ Chạy tay từng dòng codeTheo dõi dãy đã sắp, các hệ số W, mảng cộng dồn L, R và từng đáp án.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4const ll MOD = 1000000007;

5int n;

6vector<ll> f, fi;

7ll C(int a, int b) {

8 if (a < 0 || b < 0 || b > a) return 0;

9 return f[a] * fi[b] % MOD * fi[a - b] % MOD;

10}

11// W(m, j): so lan nguoi dung thu j (trong m nguoi) cam co

12ll W(int m, int j) { return (C(m - 1, j - 2) + C(m - 1, j - 1) + C(m - 1, j)) % MOD; }

13ll pw(ll a, ll e) { ll r = 1; a %= MOD; for (; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }

14int main() {

15 scanf("%d", &n);

16 vector<ll> h(n + 1);

17 for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);

18 f.assign(n + 1, 1); fi.assign(n + 1, 1);

19 for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;

20 fi[n] = pw(f[n], MOD - 2);

21 for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;

22 vector<int> id(n);

23 iota(id.begin(), id.end(), 1);

24 sort(id.begin(), id.end(), [&](int x, int y) { return h[x] < h[y]; });

25 vector<ll> s(n + 2, 0);

26 vector<int> rk(n + 1);

27 for (int j = 1; j <= n; j++) { s[j] = h[id[j - 1]]; rk[id[j - 1]] = j; }

28 ll F = 0; // tong tren moi doi

29 for (int j = 1; j <= n; j++) F = (F + s[j] % MOD * W(n, j)) % MOD;

30 vector<ll> L(n + 2, 0), R(n + 2, 0); // tong khi bo bot 1 nguoi

31 for (int j = 1; j <= n; j++) L[j] = (L[j - 1] + s[j] % MOD * W(n - 1, j)) % MOD;

32 for (int j = n; j >= 1; j--) R[j] = (R[j + 1] + s[j] % MOD * W(n - 1, j - 1)) % MOD;

33 for (int p = 1; p <= n; p++) {

34 int r = rk[p];

35 ll ans = ((F - L[r - 1] - R[r + 1]) % MOD + 2 * MOD) % MOD;

36 printf("%lld\n", ans);

37 }

38 return 0;

39}

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 35 test: subtask 1 (10 test, $N \le 15$, có cả hai ví dụ và $N = 1$), subtask 2 (9 test, $N \approx 5000$), subtask 3 (6 test, $N \approx 2\cdot 10^5$, mọi bạn cao bằng nhau), subtask 4 (10 test, $N \approx 2 \cdot 10^5$). Chiều cao được sinh đủ kiểu: ngẫu nhiên tới $10^9$, sát $10^9$ (tràn số), chỉ vài giá trị (rất nhiều bạn cao bằng nhau), đã sắp tăng/giảm, hoán vị, "tất cả bằng nhau trừ một bạn" (bẫy cho code chỉ kiểm tra vài phần tử).

Cách làm	Sub 1 (20%)	Sub 2 (30%)	Sub 3 (15%)	Sub 4 (35%)	Điểm
Cách 1 – Duyệt mọi đội	Đúng	WA/TLE	WA/TLE	WA/TLE	20
Cách 2 – Đếm đóng góp + phần bù O(N²)	Đúng	Đúng	TLE	TLE	50
Cách 3 – Cách 2 + công thức khi mọi bạn cao bằng nhau	Đúng	Đúng	Đúng	TLE	65
Cách 4 – Vandermonde + cộng dồn (sol.cpp)	Đúng	Đúng	Đúng	Đúng	100
Sai: đội chẵn chỉ tính bạn đứng thứ k/2	1/10 (WA)	WA	WA	WA	2
Sai: phần bù nhưng quên lùi vị trí các bạn đứng sau p	2/10 (WA)	WA	WA	WA	4
Sai: lấy hiệu modulo quên cộng MOD (ra số âm)	5/10 (WA)	WA	WA	WA	10
Sai: hàm C trả về int, cộng ba số int bị tràn	Đúng	WA	WA	WA	20

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: sub1.cpp được 20 điểm; sub2.cpp được 50 điểm; sub3.cpp được 65 điểm; sol.cpp được 100 điểm; wrong_lower.cpp được 2 điểm; wrong_noshift.cpp được 4 điểm; wrong_negmod.cpp được 10 điểm; wrong_int.cpp được 20 điểm. Lời giải chuẩn sol.cpp chạy test lâu nhất hết khoảng 0,2 giây, bản Python sol.py cho cùng đáp án trên mọi test (trên CPython mất khoảng 2 giây, các em nhớ chọn PyPy 3 khi nộp). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán

Cầm cờ (Đề tự luyện HSG Tin quốc gia – Bài 1)

Đề bài

Lời mở đầu

Cách 1Duyệt mọi đội – O(2^N · N log N) · 20%

Cách 2Đếm đóng góp + phần bù – O(N²) · 50%

Cách 3Khi mọi bạn cao bằng nhau – O(N) · 65%

Cách 4Đẳng thức Vandermonde – O(N log N) · 100%

Bộ test chấm "bắt" những lỗi nào?

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++