训练指南的题目。
题意是，给出n个人，以及一些关系，要求对这n个人构成一个排列，其中父亲必须排在儿子的前面。问一共有多少种方式。
做法是，对于每一个父节点，将它的儿子结点构成的子树看成无序状态，这样子对当前父节点整棵树计算一个排列数。如果把所有的这样的式子写出来，可以发现分子分母是可以相消的。假设点的总数是S，儿子的点的数目分别是A,B,C...，这样的话，对于这个结点，可以求得F(S)=F(A)+F(B)+F(C)+...。最后的结果是所有子树的F(S)*F(A)*F(B)*F(C)*...。最后消去以后就只剩下F(S)/(c(A)*c(B)*c(C)*...)，其中c(X)是结点X的子树的结点个数。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector> using namespace std; const int N = ;
map<int, int> id;
int lsf[N], pn, prm[N >> ]; void getprm() {
id.clear();
lsf[] = lsf[] = ;
pn = ;
for (int i = ; i < N; i++) {
if (!lsf[i]) {
id[i] = pn;
prm[pn++] = i;
for (int j = i; j < N; j += i) lsf[j] = i;
}
}
} typedef long long LL;
const LL MOD = ;
int cnt[N], fcn[N];
bool vis[N], fa[N];
vector<int> rel[N]; LL multi(int a, int b) {
LL ret = , p = a;
while (b > ) {
if (b & ) ret *= p, ret %= MOD;
p *= p, p %= MOD;
b >>= ;
}
return ret;
} void dfs(int x) {
cnt[x] = ;
for (vector<int>::iterator vi = rel[x].begin(); vi != rel[x].end(); vi++) {
dfs(*vi);
cnt[x] += cnt[*vi];
}
} int main() {
getprm();
int n, m, T;
scanf("%d", &T);
while (T-- && ~scanf("%d%d", &n, &m)) {
memset(vis, , sizeof(vis));
memset(cnt, , sizeof(cnt));
memset(fcn, , sizeof(fcn));
memset(fa, , sizeof(fa));
int x, y;
for (int i = ; i <= n; i++) rel[i].clear();
while (m--) {
scanf("%d%d", &x, &y);
rel[y].push_back(x);
fa[x] = true;
}
for (int i = ; i <= n; i++) if (!fa[i]) rel[].push_back(i);
dfs();
for (int i = ; i <= n; i++) {
int t = i;
while (t > ) {
fcn[id[lsf[t]]]++;
t /= lsf[t];
}
t = cnt[i];
while (t > ) {
fcn[id[lsf[t]]]--;
t /= lsf[t];
}
//cout << "~~ " << i << ' ' << cnt[i] << endl;
//for (int i = 0; i < 10; i++) cout << prm[i] << ' ' << fcn[i] << endl;
}
//cout << pn << endl;
LL ans = ;
for (int i = ; i < pn; i++) {
ans *= multi(prm[i], fcn[i]);
ans %= MOD;
}
cout << ans << endl;
}
return ;
}
——written by Lyon