1. Tính chất quan trọng của bài toán

• Giả thiết cho: "Mỗi bạn (ngoại trừ bạn chỉ làm được 1 bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn".
• Gọi ~r~ là đỉnh có ~a_r = 1~. Chọn ~r~ làm gốc của cây:
  • Nếu đi từ gốc ~r~ xuống bất kỳ nhánh lá nào, giá trị ~a_u~ luôn tăng nghiêm ngặt (vì nếu có đỉnh con ~v~ mà ~a_v < a_u~ thì theo quy nạp sẽ dẫn đến mâu thuẫn).
  • Do đó, điều kiện điểm số ~b_i > b_j~ khi ~a_i > a_j~ đồng nghĩa với việc: Điểm số ~b_u~ của các đỉnh trên mọi đường đi từ gốc ~r~ xuống lá đều phải tăng nghiêm ngặt.

2. Thuật toán đếm tổ hợp

• Bước 1: Chọn ~n~ điểm phân biệt trong ~k~ điểm của thang điểm: có ~\binom{k}{n}~ cách chọn. Vì ~k \le 10^9~ lớn nhưng ~n \le 10^5~, ta tính ~\binom{k}{n} = \frac{k(k-1)\dots(k-n+1)}{n!} \pmod{10^9 + 7}~.
• Bước 2: Với một tập ~n~ điểm số đã chọn ~\{v_1 < v_2 < \dots < v_n\}~, ta đếm số cách gán điểm vào các đỉnh của cây sao cho thỏa mãn tính chất cha < con (đây chính là bài toán đếm số thứ tự tô-pô của cây có gốc):
  • Đỉnh gốc ~r~ bắt buộc phải nhận điểm số nhỏ nhất trong tập điểm của cây con gốc ~r~.
  • Gọi ~sub[u]~ là kích thước cây con gốc ~u~.
  • Khi xét đỉnh ~u~ có tập hợp điểm kích thước ~sub[u]~: đỉnh ~u~ lấy điểm nhỏ nhất, còn lại ~sub[u] - 1~ điểm. Ta cần phân chia ~sub[u] - 1~ điểm này vào các cây con của ~u~.
  • Nếu các nút con của ~u~ lần lượt có kích thước là ~sub[v_1], sub[v_2], \dots, sub[v_m]~, số cách phân chia điểm cho các nhánh con là hệ số đa thức: ~\frac{(sub[u] - 1)!}{sub[v_1]! \cdot sub[v_2]! \dots sub[v_m]!}~
  • Nhân liên tiếp công thức này trên toàn bộ các đỉnh của cây từ dưới lên, ta thu được số cách gán điểm cho một tập ~n~ số là: ~\frac{n!}{\prod_{u=1}^n sub[u]}~
• Bước 3: Nhân kết quả: ~\text{Đáp số} = \binom{k}{n} \times \frac{n!}{\prod_{u=1}^n sub[u]} = \frac{k(k-1)\dots(k-n+1)}{\prod_{u=1}^n sub[u]} \pmod{10^9+7}~

3. Cài đặt chi tiết

• Sử dụng DFS bắt đầu từ gốc ~r~ (đỉnh có ~a_r = 1~) để tính kích thước cây con ~sub[u]~ của mọi nút.
• Nhân chia modulo bằng nghịch đảo modulo (thuật toán Euclid mở rộng hoặc lũy thừa Fermat nhỏ).
• Độ phức tạp thời gian: ~\mathcal{O}(n + \log(MOD))~ hoặc ~\mathcal{O}(n)~, bộ nhớ ~\mathcal{O}(n)~.