Editorial for Bedao Grand Contest 15 - Noel Gifts
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta có công thức để tính giá trị kỳ vọng là ~S / \binom{M + 1}{2}~, với:
~S~ là tổng độ đa dạng của mọi cặp (~L, R~) có thể chọn.
~\binom{M + 1}{2}~ là số lượng cặp (~L, R~) thỏa mãn ~1 \le L \le R \le M~, dễ thấy đây là một hằng số.
Vì các cặp số (~L, R~) có xác suất được chọn bằng nhau nên ta thu được công thức trên. Ngoài ra, mẫu số là hằng số nên ~S~ tỉ lệ thuận với giá trị kỳ vọng, bài toán tương đương đếm số cách chia quà vào các túi sao cho ~S~ đạt giá trị lớn nhất có thể.
Đến đây, ta sẽ đi tính contribution của từng loại quà vào tổng ~S~, nói ngắn gọn là với loại quà thứ ~i~, ta cần tính xem có bao nhiêu cặp (~L, R~) mà đảm bảo ông già Noel lấy được ít nhất một hộp quà loại thứ ~i~. Vậy ta có 2 trường hợp sau:
Trường hợp 1: ~a_i \le M~.
Với mỗi túi chứa ít nhất một hộp quà loại ~i~, ta đánh số cho chúng lần lượt từ trái sang phải là ~0, 1, \dots, a_i + 1~, trong đó túi số ~0~ ở vị trí ~0~ và túi số ~a_i + 1~ ở vị trí ~M + 1~ tính từ trái sang (hiển nhiên 2 túi quà này không hề tồn tại mà chỉ là quy ước). Gọi ~diff_k~ là khoảng cách từ túi thứ ~k~ đến túi quà gần nhất về bên phải của nó mà chứa hộp quà loại ~i~.
Để tính contribution của các hộp quà thuộc loại ~i~, ta có công thức: ~\binom{M + 1}{2} - \sum_{k = 0}^{a_i}\binom{diff_k}{2}~.
~\binom{M + 1}{2}~ là số lượng cặp (~L, R~) thỏa mãn ~1 \le L \le R \le M~.
~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ là số lượng cặp (~L, R~) mà không túi nào từ ~L~ đến ~R~ có hộp quà thuộc loại ~i~.
Vậy theo nguyên tắc loại trừ ta thu được công thức trên, mặt khác vì ~\binom{M + 1}{2}~ là một hằng số nên để contribution là tối đa thì ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ phải đạt giá trị tối thiểu. Ngoài ra, cần thỏa mãn một điều kiện hiển nhiên là ~\sum_{k = 0}^{a_i} diff_k = M + 1~.
Nhận xét: ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ đạt giá trị tối thiểu khi và chỉ khi chênh lệch tối đa giữa 2 phần tử thuộc dãy ~diff_0, \dots, diff_{a_i}~ là không quá ~1~.
Chứng minh: Nếu ~diff_1 - diff_0 > 1~ thì ~\binom{diff_1}{2} + \binom{diff_0}{2} > \binom{diff_1 - 1}{2} + \binom{diff_0 + 1}{2}~ dẫn đến tổng ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ không đạt giá trị tối thiểu (tương tự với các cặp phần tử khác).
Vậy ta cần đếm số dãy ~diff_0, \dots, diff_{a_i}~ thỏa mãn:
Chênh lệch tối đa giữa 2 phần tử không quá ~1~.
~\sum_{k = 0}^{a_i} diff_k = M + 1~.
Nhận xét: Gọi ~x~ là số phần tử có giá trị khác ~min(diff_0, \dots, diff_{a_i})~, dễ thấy ~x < a_i + 1~. Mặt khác, vì chênh lệch giữa 2 phần tử bất kỳ không vượt quá ~1~ đơn vị nên ~min(diff_0, \dots, diff_{a_i}) = (M + 1 - x) / (a_i + 1)~. Vì vậy, chỉ có duy nhất 1 giá trị phù hợp là ~x = (M + 1) \mod (a_i + 1)~.
Kết luận: Đặt ~z = (M + 1 - x) / (a_i + 1)~ thì:
~S_{max} = \binom{M + 1}{2} - (a_i + 1 - x) \cdot \binom{z}{2} - x \cdot \binom{z + 1}{2}~.
Số cách chia dãy thỏa mãn là ~\binom{a_i + 1}{x}~.
Trường hợp 2: ~a_i \gt M~.
Đây là 1 corner case có thể khiến thí sinh mất điểm nhưng một khi nhận ra thì rất dễ giải quyết. Vì ~a_i > M~ nên ta cứ chia sẵn 1 hộp quà vào mỗi túi, lúc này ~(a_i - M)~ hộp quà còn lại được phép chia tùy ý vì chúng không ảnh hưởng đến tổng ~S~. Để tính số cách, ta chỉ việc áp dụng trực tiếp công thức chia kẹo Euler.
Kết luận:
~S_{max} = \binom{M + 1}{2}~.
Số cách chia dãy thỏa mãn là ~\binom{a_i - 1}{M - 1}~.
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5, MAX = 1e6 + 5, MOD = 998'244'353; int T, n, m; int a[N]; int gt[MAX], inv[MAX]; int Pow(int A, int B) { int ans = 1; while (B) { if (B & 1) ans = 1ll * ans * A % MOD; A = 1ll * A * A % MOD, B >>= 1; } return ans; } void prepare() { gt[0] = 1; for (int i = 1; i < MAX; i++) gt[i] = 1ll * gt[i - 1] * i % MOD; inv[MAX - 1] = Pow(gt[MAX - 1], MOD - 2); for (int i = MAX - 1; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % MOD; } int C(int k, int n) { if (k < 0 || k > n) return 0; return 1ll * gt[n] * inv[k] % MOD * inv[n - k] % MOD; } int C2(int n) { if (n < 2) return 0; return (1ll * n * (n - 1) / 2) % MOD; } void add(int &A, int B) { A += B; if (A >= MOD) A -= MOD; } void sub(int &A, int B) { add(A, MOD - B); } int main() { cin.tie(0) -> sync_with_stdio(0); if (fopen("temp.inp", "r")) { freopen("temp.inp", "r", stdin); freopen("temp.out", "w", stdout); } cin >> T; cin >> n >> m; for (int i = 1; i <=n; i++) cin >> a[i]; if (T == 1) { int sum = 0, choose = C2(m + 1); for (int i = 1; i <= n; i++) { add(sum, choose); if (a[i] <= m) { int x = (m + 1) % (a[i] + 1); int z = (m + 1) / (a[i] + 1); sub(sum, 1ll * (a[i] + 1 - x) * C2(z) % MOD); sub(sum, 1ll * x * C2(z + 1) % MOD); } } cout << 1ll * sum * Pow(choose, MOD - 2) % MOD << '\n'; } else { prepare(); int sum = 1; for (int i = 1; i <= n; i++) { if (a[i] <= m) { int x = (m + 1) % (a[i] + 1); sum = 1ll * sum * C(x, a[i] + 1) % MOD; } else sum = 1ll * sum * C(m - 1, a[i] - 1) % MOD; } cout << sum << '\n'; } return 0; }
Comments