Editorial for Bedao Grand Contest 16 - Thưởng Tết
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Duyệt tất cả các cách chia thưởng.
Subtask2
Vì cấp trên trực tiếp của tất cả các nhân viên chính là chủ tịch nên mức thưởng cho từng nhân viên độc lập với nhau. Số cách chia thưởng đúng bằng chỉnh hợp chập ~n~ của ~m~:
~\frac{m!}{(m-n)!}~
Subtask3
Đồ thị có dạng hình một đường thẳng. Vì ta chỉ cần quan tâm đến thứ tự về mức thưởng của ~n~ nhân viên, nên ta đếm số thứ tự rồi nhân với ~\binom{m}{n}~. Từ giờ ta coi một cách chia thưởng là một hoán vị của các số nguyên từ ~1~ đến ~n~.
Gọi ~dp(i, j)~ là số cách chia thưởng đến nhân viên thứ ~i~ mà anh ta được xếp ở vị trí thứ ~j~ (về mức thưởng). Xét trường hợp ~a_{i-1} < a_i~, ta có công thức: ~dp(i, j) = \sum_{k=j}^{i-1}dp(i-1, k)~
Phần tính tổng ở hai biểu thức trên ta có thể dùng prefix sum để tính nhanh. Như vậy độ phức tạp thuật toán là ~O(n ^ 2 + m)~.
Subtask 4
Vì ~a_i = i, p_i < i~ nên mức thưởng của một nhân viên luôn lớn hơn mức thưởng của cấp trên. Đồ thị có dạng anti-arborescence (cây có hướng, mà các cạnh luôn hướng từ dưới lên).
Gọi ~dp(u)~ là số cách chia thưởng cho cây con gốc u. Để tính ~dp(u)~, trước hết ta tính ~dp~ cho các nút con. Gọi ~dp(v_1), dp(v_2), . . . , dp(v_k)~ là kết quả tính được cho các nút con của ~u~ là ~v_1, v_2, . . . , v_k~. Vì cách chia thưởng cho các nút con là độc lập với nhau, nên ta áp dụng tổ hợp:
~dp(u) = dp(v_1)dp(v_2)...dp(v_k)\binom{sz(u) - 1}{sz(v_1)}\binom{sz(u) - 1 - sz(v_1)}{sz(v_2)}...\binom{sz(u) - 1 - sz(v_1) - ... - sz(v_{k-1})}{sz(v_k)}~
với ~sz(u)~ là số đỉnh trong cây con gốc ~u~. Rút gọn công thức trên, ta được:
~dp(u) = dp(v_1)dp(v_2)...dp(v_k)\frac{(sz(u) - 1)!}{sz(v_1)!sz(v_2)!...sz(v_k)!}~
Áp dụng công thức quy hoạch động trên ta được thuật toán ~O(n + m)~.
Subtask 5
Đồ thị đã cho có dạng polytree (cây có hướng). Ta sẽ mở rộng thuật toán ở Subtask 3.
Gọi ~dp(u, i)~ là số cách chia thưởng cho cây con gốc ~u~, mà ~u~ đứng ở vị trí ~i~. Ban đầu ta tính ~dp~ cho các nút con ~v~. Bài toán đặt ra là cần phải gộp cách chia thưởng cho cây con gốc ~v~ với cách chia thưởng cho cây con gốc ~u~. Nói cách khác, ta cần tìm cách gộp ~dp(v, j)~, ~dp(u, i)~ thành ~dp(u, k)~. Xét trường hợp ~a_u > a_v~. Dưới đây mô tả vị trí của các nút:
~\underbrace{...v...}_{k-1}u...~
Phần phía trước ~u~ có ~k-1~ phần tử, trong đó bao gồm ~i-1~ phần tử thuộc cây con gốc ~u~ (trước khi gộp). Như vậy phần trống còn lại để xếp các nút thuộc cây con gốc ~v~ là ~k - i~. Để ~v~ nằm trong phần trống đó thì ~j \leq k - i~. Vì vậy, phần phía trước ~u~ sẽ có ~k - i~ phần tử thuộc cây con gốc ~v~, và đằng sau sẽ có ~sz(v) - (k - i)~. Vậy số cách xếp để gộp vào ~dp(u, k)~ sẽ là:
~dp(u,i)dp(v,j)\binom{k-1}{k-i}\binom{sz(u)+sz(v)-k}{sz(v)-(k-i)}~
Tương tự với trường hợp ~a_u < a_v~:
~\underbrace{...}_{k-1}u...v...~
Phần phía sau ~u~ có ~sz(u) + sz(v) - k~ phần tử, trong đó bao gồm ~sz(u) - i~ phần tử thuộc cây con gốc ~u~ (trước khi gộp). Như vậy phần trống còn lại để xếp các nút thuộc cây con gốc ~v~ là ~sz(v) + i - k~. Để ~v~ nằm trong phần trống đó thì ~sz(v) - j + 1 \leq sz(v) + i - k~, tức là ~j > k - i~. Vì vậy, phần phía sau ~u~ sẽ có ~sz(v) + i - k~ phần tử thuộc cây con gốc ~v~, và phần phía trước sẽ có ~k - i~. Vậy số cách xếp để gộp vào ~dp(u, k)~ sẽ là:
~dp(u,i)dp(v,j)\binom{k-1}{k-i}\binom{sz(u)+sz(v)-k}{sz(v)+i-k}~
Ta thấy rằng hai công thức trên giống hệt nhau, chỉ khác ở điều kiện giữa ~i~, ~j~ và ~k~. Duyệt qua từng ~i~, ~j~, ~k~ như trên, ta được thuật toán ~O(n ^ 3)~.
Subtask 6
Ta tiếp tục cải tiến Subtask 5. Ta thấy là trừ phần ~dp(v, j)~ ra thì phần tổ hợp không phụ thuộc vào ~j~. Xét trường hợp ~a_u > a_v~. Vì ~j \leq k - i~ nên ta dùng prefix sum để lấy tổng tất cả các giá trị ~dp(v, j)~ từ ~1~ đến ~k - i~. Công thức trên sẽ trở thành:
~dp(u,k) = dp(u,i)\sum_{j=1}^{k-i}dp(v,j)\binom{sz(u) + sz(v) - k}{sz(v) + i - k}~
Để đạt được thuật toán ~O(n ^ 2)~, ta cần chặt các điều kiện của ~i~, ~k~ để duyệt. Ở hai biểu thức ở trên, ta nhận được hai bất phương trình:
~k-i\geq 0~
~sz(v) + i - k\geq 0~
Gộp lại ta được:
~i \leq k \leq i + sz(v)~
Như vậy ~k~ duyệt xấp xỉ ~sz(v)~ lần, và ~i~ duyệt xấp xỉ ~sz(u)~ lần. Tại mỗi nút ~u~, việc duyệt như này tương đương với việc duyệt qua từng cặp đỉnh thuộc hai cây con khác nhau trong cây con gốc ~u~. Như vậy độ phức tạp thuật toán là ~O(n ^ 2)~, vì mỗi cặp trên cây chỉ duyệt qua đúng một lần.
#include <bits/stdc++.h> const int maxN = 3e3 + 10; const long long mod = 998244353; long long fact[1000010], inv_fact[1000010]; long long powmod(long long a, long long b) { long long ans = 1; while (b) { if (b & 1) { ans = ans * a % mod; } b /= 2; a = a * a % mod; } return ans; } long long nCk(int n, int k) { if (k < 0 || k > n) { return 0; } return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod; } int n, m, p[maxN], a[maxN], sz[maxN], dp[maxN][maxN], f[maxN]; long long sum_dp[maxN]; void solve() { std::cin >> n >> m; for (int i = 1; i <= n; i++) { std::cin >> p[i]; } for (int i = 1; i <= n; i++) { std::cin >> a[i]; } std::fill(sz, sz + n + 1, 1); for (int i = 0; i <= n; i++) { dp[i][1] = 1; } long long ans = nCk(m, n), total_sz = 0; for (int v = n; v; v--) { int u = p[v]; if (u == 0) { total_sz += sz[v]; ans = ans * nCk(total_sz, sz[v]) % mod; long long sum = 0; for (int j = 1; j <= sz[v]; j++) { sum += dp[v][j]; } sum %= mod; ans = ans * sum % mod; continue; } sum_dp[0] = 0; for (int j = 1; j <= sz[v]; j++) { sum_dp[j] = (sum_dp[j - 1] + dp[v][j]) % mod; } std::fill(f + 1, f + sz[u] + sz[v] + 1, 0); if (a[v] < a[u]) { for (int i = 1; i <= sz[u]; i++) { for (int k = i; k <= i + sz[v]; k++) { f[k] = (f[k] + dp[u][i] * sum_dp[k - i] % mod * nCk(k - 1, i - 1) % mod * nCk(sz[u] + sz[v] - k, sz[u] - i)) % mod; } } } else { for (int i = 1; i <= sz[u]; i++) { for (int k = i; k <= i + sz[v]; k++) { f[k] = (f[k] + dp[u][i] * (sum_dp[sz[v]] - sum_dp[k - i] + mod) % mod * nCk(k - 1, i - 1) % mod * nCk(sz[u] + sz[v] - k, sz[u] - i)) % mod; } } } sz[u] += sz[v]; std::copy(f + 1, f + sz[u] + 1, dp[u] + 1); } std::cout << ans; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); // if (std::ifstream("BONUS.INP")) { // std::freopen("BONUS.INP", "r", stdin); // std::freopen("BONUS.OUT", "w", stdout); // } fact[0] = 1; for (int i = 1; i <= (int)(1e6); i++) { fact[i] = fact[i - 1] * i % mod; } inv_fact[(int)(1e6)] = powmod(fact[(int)(1e6)], mod - 2); for (int i = (int)(1e6) - 1; i >= 0; i--) { inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod; } int T = 1; // std::cin >> T; while (T--) { solve(); } }
Comments