1. Phân tích bài toán

• Trên một đồ thị có hướng bất kỳ (General DAG), bài toán đếm số lượng thứ tự tô-pô là bài toán #P-complete (cực khó, chỉ chạy được ~N \le 20~ bằng quy hoạch động bitmask).
• Tuy nhiên, khi đồ thị có hướng là một Cây có gốc (Arborescence / Directed Tree) hướng từ gốc xuống lá, ta có thể giải quyết trong thời gian tuyến tính ~\mathcal{O}(N)~.

2. Ý tưởng Quy hoạch động / Tổ hợp trên cây

• Xét cây con gốc ~u~, gọi ~sub[u]~ là số lượng đỉnh trong cây con gốc ~u~.
• Đỉnh ~u~ là gốc của cây con nên ~u~ bắt buộc phải xuất hiện trước tất cả các đỉnh con cháu của nó (tức nhận vị trí đầu tiên trong đoạn ~sub[u]~ phần tử).
• Còn lại ~sub[u] - 1~ vị trí cho các cây con trực tiếp ~v_1, v_2, \dots, v_m~ của ~u~:
  • Số cách chọn các vị trí phân phối cho từng nhánh con là hệ số đa thức (multinomial coefficient): ~\binom{sub[u] - 1}{sub[v_1], sub[v_2], \dots, sub[v_m]} = \frac{(sub[u] - 1)!}{sub[v_1]! \cdot sub[v_2]! \dots sub[v_m]!}~
  • Trong nội bộ mỗi nhánh con ~v_i~, lại có ~dp[v_i]~ cách sắp xếp thứ tự nội bộ hợp lệ.
  • Do đó: ~dp[u] = (sub[u] - 1)! \times \prod_{v \in children(u)} \frac{dp[v]}{sub[v]!}~

3. Rút gọn công thức

• Khi triển khai đệ quy công thức trên từ gốc ~R~ xuống các lá, tất cả các thừa số giai thừa ~(sub[v] - 1)!~ ở tử số sẽ triệt tiêu với các mẫu số ~sub[v]!~, để lại đúng mẫu số ~sub[v]~!
• Cụ thể: ~dp[R] = \frac{N!}{\prod_{u=1}^N sub[u]} \pmod{10^9 + 7}~

4. Thuật toán

1. Dùng thuật toán DFS bắt đầu từ gốc ~R~:
   • Tính kích thước cây con ~sub[u]~ cho mọi đỉnh ~u~.
   • Đồng thời tính tích các ~sub[u]~ theo modulo ~10^9 + 7~.
2. Tính ~N! \pmod{10^9 + 7}~.
3. Lấy ~N! \times \left(\prod_{u=1}^N sub[u]\right)^{-1} \pmod{10^9 + 7}~ bằng định lý Fermat nhỏ: ~x^{-1} \equiv x^{MOD-2} \pmod{MOD}~.

• Độ phức tạp thời gian: ~\mathcal{O}(N + \log(MOD))~.