P4099 [HEOI2013] SAO
题意
给你一棵 \(n\) 个点的树，每条边 \((u,v)\) 有一个参数 \(c\) 表示 \(u,v\) 谁必须放在前面。
求有多少种排列，使得所有边都满足条件。
\(n \le 1000\)。
（题意其实对原题做了一丁点转化）
思路
本来想补补 zr2024 B 班的题。然后刚好发现上上周多校杂题选讲也讲了这题。这下不得不补了。
考虑容斥。
我们把 \(1\) 看作根，对于边 \((fa,u)\)，\(c=0\) 表示 \(fa\) 先，\(c=1\) 表示 \(u\) 先。
我们先把所有 \(c=1\) 看作无限制，求方案数，然后减去有一个 \(c=1\) 被钦定成 \(c=0\) 的方案数，然后再加上有两个 \(c=1\) 被钦定成 \(c=0\) 的方案数，以此类推。
这段做法不够优美，不建议阅读。
考虑再树形 DP 中带上容斥系数。
朴素 DP：
设 \(f_{u,p,s}\) 表示 \(u\) 的子树中，\(u\) 在排列的第 \(p\) 位，有 \(s\) 个 \(c=1\) 被钦定成 \(c=0\) 的方案数。
这样复杂度超了。
我们把这一维改成 \(0/1\) 表示 \(s\) 的奇偶性，也是一样的。
看来上上周的 ppt，我这个是什么杂糅做法，我们还是来一个小清新容斥做法吧。
我们会外向树拓扑序计数，即父亲的必须在儿子前面：
证明：对于随机排列，一个点 \(u\) 有 \(siz_u\) 的概率在它子树的所有点的前面。
那么我们有一些 \(c\) 没有限制，就相当于把原树割成了若干棵外向树。每个连通块计数然后乘起来即可。
所以设 \(f_{u,s,0/1}\) 表示满足 \(u\) 的连通块大小为 \(s\)，钦定 \(c=1\) 变成 \(0\) 的边的奇偶性为 \(0/1\)，\(u\) 的整棵子树的方案数。
事实上不需要 \(0/1\) 那维，转移的时候带上容斥系数就好。
时间复杂度是树形背包复杂度，是 \(O(n^2)\)。
具体怎么转移见代码。
解释一下转移系数：
合并 \(u,v\) 时，子树 \(u,v\) 内部已经有序，所以只需要再乘上组合数 \(\binom{siz_u+siz_v}{siz_v}\)。
但是这样合并完所有儿子之后 \(u\) 所在连通块不一定符合拓扑序。
\(u\) 所在连通块的贡献应该为 \(\frac{s_u!}{\prod s_i}\)。现在它的贡献是啥？合并 \(u,v\) 时会贡献 \(\frac{(s_u+s_v)!}{s_u!s_v!} \times \frac{s_v!}{\prod_{i \in T_v} s_i}\)（\(T_v\) 表示 \(v\) 的连通块的点集）。
合并完所有儿子之后很多都会消掉，剩下 \(\frac{s_u!}{\prod_{i \in T_u \land i \neq u} s_i}\)
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {#define gc getchar_unlockedconstexpr int N=1e3+7,mod=1e9+7;struct modint {int x;modint (int _x=0): x(_x) {}modint operator + (modint b) const { return x+b.x < mod ? x+b.x : x+b.x-mod; }modint operator - (modint b) const { return x+mod-b.x < mod ? x+mod-b.x : x-b.x; }modint operator * (modint b) const { return 1ll*x*b.x%mod; }modint &operator += (modint b) { return *this = *this + b; }modint &operator -= (modint b) { return *this = *this - b; }modint &operator *= (modint b) { return *this = *this * b; }modint inv () const { int b=mod-2;modint s(1),a=*this;while(b) {if(b&1) s*=a;a*=a;b>>=1;}return s;}void write() const { pf("%d\n",x); }};int T,n;struct pii {int v,c;};vector<pii> son[N];int siz[N];modint f[N][N],g[N];modint fac[N],inv[N],ifac[N];modint binom[N][N];void clear() {rep(i,1,n) son[i].clear();memset(f,0,sizeof(f));}void init() {fac[0]={1};rep(i,1,n) fac[i]=fac[i-1]*(modint){i};ifac[n]=fac[n].inv();per(i,n-1,0) ifac[i]=ifac[i+1]*(modint){i+1};inv[1]=1;rep(i,2,n) inv[i]=inv[mod%i]*(mod-mod/i);binom[0][0]=1;rep(i,1,n) {binom[i][0]=1;rep(j,1,n) binom[i][j]=binom[i-1][j-1]+binom[i-1][j];}}void dfs(int u,int fa) {f[u][1]={1};siz[u]=1;for(pii p : son[u]) if(p.v^fa) {int v=p.v;int op=p.c;dfs(v,u);memset(g,0,sizeof(g));rep(i,1,siz[u]) {rep(j,1,siz[v]) {if(op) {g[i]+=f[u][i]*f[v][j]*binom[siz[u]+siz[v]][siz[v]];g[i+j]-=f[u][i]*f[v][j]*binom[siz[u]+siz[v]][siz[v]];} else {g[i+j]+=f[u][i]*f[v][j]*binom[siz[u]+siz[v]][siz[v]];}}}memcpy(f[u],g,sizeof(g));siz[u]+=siz[v];}rep(i,1,siz[u]) f[u][i]*=inv[i];}void main() {sf("%d",&T);n=N-7;init();while(T--) {sf("%d",&n);clear();rep(i,1,n-1) {int u,v;char c;sf("%d",&u);++u;c=gc();while(c!='<' && c!='>') c=gc();sf("%d",&v);++v;if(c=='>') swap(u,v);son[u].push_back({v,0}), son[v].push_back({u,1});}dfs(1,0);modint ans={0};rep(i,1,n) {ans+=f[1][i];}ans.write();}}
}
int main() {#ifdef LOCALfreopen("in.txt","r",stdin);freopen("my.out","w",stdout);#endifwing_heart :: main();
}
)
)
)
