(周赛t4)1916. 统计为蚁群构筑房间的不同顺序
2021-09-17 本文已影响0人
来到了没有知识的荒原
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];
}
};