(周赛t4)1916. 统计为蚁群构筑房间的不同顺序

1916. 统计为蚁群构筑房间的不同顺序

又用到了乘法逆元，记好公式：
算是一个树上dp，计算拓扑排序的数量。
yxc的题解

typedef long long ll;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int e[N], ne[N], h[N], idx;
ll sz[N], ans[N];
ll f[N], g[N];
class Solution {
 public:
  ll qmi(ll a, ll b) {
    ll res = 1;
    while (b) {
      if (b & 1) res = (res * a) % MOD;
      a = (a * a) % MOD;
      b >>= 1;
    }
    return res;
  }
  void dfs(int u) {
    ll s = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
      int j = e[i];
      dfs(j);
      s += sz[j];
    }
    ll res = f[s];

    for (int i = h[u]; i != -1; i = ne[i]) {
      int j = e[i];
      res = (res * g[sz[j]] % MOD * ans[j] % MOD);
    }
    ans[u] = res;
    sz[u] = s + 1;
  }
  void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
  int waysToBuildRooms(vector<int>& pa) {
    idx = 0, memset(h, -1, sizeof h);
    memset(sz, 0, sizeof sz), memset(ans, 0, sizeof ans);
    f[0] = g[0] = 1;
    for (int i = 1; i < N; i++) {
      f[i] = f[i - 1] * i % MOD;
      g[i] = qmi(f[i], MOD - 2) % MOD;
    }

    for (int i = 1; i < pa.size(); i++) {
      add(pa[i], i);
    }
    dfs(0);
    return ans[0];
  }
};