P12639 [UOI 2020] Topological Sorting of a Tree
题解
定理
对于一颗外向树,其拓扑序数量为:
∑i=1nszin!
这个东西的证明类似于把根节点放在最前面,然后对每个子树分别统计。
我们发现,< 满足外向树的性质,所以我们只需要关注 > 造成的影响即可。
考虑容斥,设 S 中的内向边变成外向边,其余的任意,则容斥系数显然为 (−1)∣S∣,所有任意的地方我们可以将两边的组合起来,具体的,要合并大小为 x 和 y 的排列数分别为 gx 和 gy 的树,最终结果为 gx⋅gy⋅(xx+y)。
具体的,考虑树形 DP:f[u][i][j] 表示 u 所在连通块大小为 i,钦定了 j 条边的方案数,很明显直接转移是 O(n3) 的,考虑优化。
我们发现,j 实际上只参与容斥系数的计算,我们不妨直接将 (−1)j 塞进 f 里,因此状态为:f[u][i] 表示 u 所在联通块中有 i 个点的方案数。
考虑根据 u 的儿子 v 之间的 (u,v) 转移:
重要
注意,拓扑序公式中每个大小为 x 的连通块都应乘上 x1,这个放到最后乘,以下式子中不讨论。
- (u,v) 为外向边,此时上面新的贡献阶乘应为 (sizu+sizv)!,显然底下的是对的,因此:
f[u][i+j]←f[u][i]⋅f[v][j]⋅sizu!⋅sizv!(sizu+sizv)!
- (u,v) 为内向边,此时我们可以钦定也可以任意,任意的贡献就是拓扑序相穿插,钦定为
<的贡献与前面相同,但多一个 −1:f[u][i]←f[u][i]⋅f[v][j]⋅(sizusizu+sizv)
f[u][i+j]←−f[u][i]⋅f[v][j]⋅sizu!⋅sizv!(sizu+sizv)!
注意每次做完以后要 f[u][i]←f[u][i]⋅i1。
时间复杂度 O(n2)。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 3e3+10 , M = N*2;
const int MOD = 1e9+7;
int n;
int h[N] , e[M] , ne[M] , w[M] , idx;
int fac[N] , invfac[N];
int f[N][N] , g[N] , siz[N];
void add(int &x , int y) {
x += y;
if(x >= MOD) x -= MOD;
}
void sub(int &x , int y) {
x -= y;
if(x < 0) x += MOD;
}
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;
}
int C(int x , int y) {
return 1ll * fac[x] * invfac[y] % MOD * invfac[x-y] % MOD;
}
void add(int a , int b , int c) {
w[idx] = c , e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
void init() {
fac[0] = 1;
for(int i = 1 ; i <= n ; i ++)
fac[i] = 1ll * fac[i-1] * i % MOD;
invfac[n] = qmi(fac[n] , MOD-2);
for(int i = n ; i >= 1 ; i --)
invfac[i-1] = 1ll * invfac[i] * i % MOD;
}
void dfs(int u) {
siz[u] = 1; f[u][1] = 1;
for(int i = h[u] ; ~i ; i = ne[i]) {
int v = e[i];
dfs(v);
for(int a = 1 ; a <= siz[u] ; a ++)
for(int b = 1 ; b <= siz[v] ; b ++) {
if(!w[i]) {
add(g[a+b] , 1ll * f[u][a] * f[v][b] % MOD
* C(siz[u] + siz[v] , siz[u]) % MOD);
} else {
add(g[a] , 1ll * f[u][a] * f[v][b] % MOD
* C(siz[u] + siz[v] , siz[u]) % MOD);
sub(g[a+b] , 1ll * f[u][a] * f[v][b] % MOD
* C(siz[u] + siz[v] , siz[u]) % MOD);
}
}
siz[u] += siz[v];
memcpy(f[u] , g , sizeof g);
memset(g , 0 , sizeof g);
}
for(int i = 1 ; i <= siz[u] ; i ++)
f[u][i] = 1ll * f[u][i] * fac[i-1] % MOD * invfac[i] % MOD;
}
int main() {
scanf("%d" , &n);
init();
memset(h , -1 , sizeof h);
for(int v = 2 ; v <= n ; v ++) {
int u; char c;
scanf("%d %c" , &u , &c);
add(u , v , c=='>');
}
dfs(1);
int ans = 0;
for(int i = 1 ; i <= n ; i ++)
add(ans , f[1][i]);
printf("%d\n" , ans);
return 0;
}