Count Ways to Build Rooms in an Ant Colony LeetCode solution in C++

1
class Solution {
2
 public:
3
  int waysToBuildRooms(vector<int> &prevRoom) {
4
    int n = prevRoom.size();
5

6
    vector<long> fact(n + 1, 1), inv_fact(n + 1, 1), inv(n + 1, 1);
7
    for (int i = 2; i <= n; ++i) {
8
      inv[i] = mod - mod / i * inv[mod % i] % mod;
9
      fact[i] = fact[i - 1] * i % mod;
10
      inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
11
    }
12

13
    vector<vector<int>> children(n);
14
    for (int i = 1; i < n; ++i) {
15
      children[prevRoom[i]].push_back(i);
16
    }
17

18
    return postorder(children, fact, inv_fact, 0).first;
19
  }
20

21
 private:
22
  long mod = 1e9 + 7;
23

24
  pair<long, long> postorder(const vector<vector<int>> &children, const vector<long> &fact,
25
                             const vector<long> &inv_fact, int curr) {
26
    if (children[curr].size() == 0) return {1, 1};
27
    long tot_ways = 1, my_size = 1;
28
    for (int child : children[curr]) {
29
      auto [ways, size_of] = postorder(children, fact, inv_fact, child);
30
      tot_ways = ((tot_ways * ways) % mod) * inv_fact[size_of] % mod;
31
      my_size += size_of;
32
    }
33
    return {(tot_ways * fact[my_size - 1]) % mod, my_size};
34
  }
35
};