Tap here to switch tabs
Problem
Submissions

Problem: Count Ways to Build Rooms in an Ant Colony

Count Ways to Build Rooms in an Ant Colony gives each room a prerequisite and asks for the number of valid orders that build every room, starting from room zero, modulo a large prime.

Statement

You are tasked with building an ant colony consisting of nn rooms labeled from 00 to n−1n - 1. The construction dependencies are specified by an integer array prevRoom of length nn, where prevRoom[i] represents the room that must be built before room i can be built.

Room 00 is the starting point of the colony and has no prerequisite, indicated by prevRoom[0] being −1-1. For every other room i, you may only build room i after room prevRoom[i] has already been completed.

Return the number of distinct valid orders in which all nn rooms can be built. Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • n ==== prevRoom.length

  • 2≤2 \leq n ≤105\leq 10^5

  • prevRoom[0] ==−1== -1

  • 0≤0 \leq prevRoom[i] << n for all 1≤1 \leq i << n

  • Every room is reachable from room 00 once all the rooms are built.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Ways to Build Rooms in an Ant Colony

Count Ways to Build Rooms in an Ant Colony gives each room a prerequisite and asks for the number of valid orders that build every room, starting from room zero, modulo a large prime.

Statement

You are tasked with building an ant colony consisting of nn rooms labeled from 00 to n−1n - 1. The construction dependencies are specified by an integer array prevRoom of length nn, where prevRoom[i] represents the room that must be built before room i can be built.

Room 00 is the starting point of the colony and has no prerequisite, indicated by prevRoom[0] being −1-1. For every other room i, you may only build room i after room prevRoom[i] has already been completed.

Return the number of distinct valid orders in which all nn rooms can be built. Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • n ==== prevRoom.length

  • 2≤2 \leq n ≤105\leq 10^5

  • prevRoom[0] ==−1== -1

  • 0≤0 \leq prevRoom[i] << n for all 1≤1 \leq i << n

  • Every room is reachable from room 00 once all the rooms are built.