Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

1916. Count Ways to Build Rooms in an Ant Colony – Đếm số cách xây các phòng trong tổ kiến (LeetCode, độ khó Hard)

Bạn là một chú kiến được giao nhiệm vụ xây thêm ~n~ phòng mới, đánh số từ ~0~ đến ~n - 1~, cho tổ của mình. Bạn được cho bản kế hoạch mở rộng dưới dạng một mảng số nguyên prevRoom độ dài ~n~ (chỉ số tính từ 0), trong đó prevRoom[i] cho biết bạn phải xây phòng prevRoom[i] trước khi xây phòng ~i~, và hai phòng này phải được nối trực tiếp với nhau. Phòng ~0~ đã được xây sẵn, nên prevRoom[0] = -1. Bản kế hoạch đảm bảo rằng khi xây xong tất cả các phòng thì mọi phòng đều đi tới được từ phòng ~0~.

Mỗi lúc bạn chỉ xây được một phòng, và bạn chỉ có thể đi lại tự do giữa các phòng đã xây nếu chúng được nối với nhau. Bạn có thể chọn xây bất kỳ phòng nào miễn là phòng trước nó đã được xây.

Hãy in ra số thứ tự khác nhau để xây tất cả các phòng. Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu là số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên prevRoom[0], prevRoom[1], ..., prevRoom[n-1] (số đầu tiên luôn là ~-1~).

Kết quả

• Một số nguyên là đáp án của bài.

Giới hạn

• ~2 \le n \le 10^5~
• prevRoom[0] = -1; ~0 \le~ prevRoom[i] ~< n~ với mọi ~1 \le i < n~.
• Khi xây xong tất cả, mọi phòng đều đi tới được từ phòng ~0~.

Sample Input 1

3
-1 0 1

Sample Output 1

1

Giải thích

Chỉ có đúng một cách xây các phòng: 0 → 1 → 2.

Sample Input 2

5
-1 0 0 1 2

Sample Output 2

6

Giải thích

6 cách là: 0 → 1 → 3 → 2 → 4; 0 → 2 → 4 → 1 → 3; 0 → 1 → 2 → 3 → 4; 0 → 1 → 2 → 4 → 3; 0 → 2 → 1 → 3 → 4; 0 → 2 → 1 → 4 → 3.