一种dag图不等式计数

Solution :

首先对于等号连通的部分可以缩点,之后变成了只由<构成的\rm DAG不等式

因为事\rm DAG,所以直链部分可以直接继承,对于有多个支链的点,考虑两个支链不等式怎么合成

假设现在变成拓扑排序下的树上\rm dp

f_{u,x}表示u子树中的点被小于号分割成了x段的方案数,那么对于任意两个支链u,v,有

f_{u,x}=f'_{u,j}\times f_{v,k}\times g_{j,k,x}

是一个树上背包合并的形式,带了一个合并系数g_{j,k,x}表示长度为j,k的段合成为长度x的段的方案数。

因为不等式同类不能直接合并,因此可以钦点两个不等式链的对位,在合并长度为x的链上,首先钦点j个位置固定,然后剩下x-j个位置可以落一些k链上的点进去,如果直接在j链上钦点重叠位的位置,那就可以直接确定k链上所有点的相对位置,所以

g_{j,k,x}=\binom{x}{j}\binom{j}{j+k-x}

但是如果直接在一条链中钦点对于哪些点重叠,两条链剩下点(非重叠点)的相对位置会较难确定。

因为u节点始终是独立点,所以j实际为j-1xx-1

总复杂度O(n^3)

Solution Ex:

复杂度O(n^2) 的高明做法

给定一个内向森林,祖先节点的颜色必须严格大于后代,颜色必须是连续的正整数,求方案

g(n)表示所有节点有n种颜色并且满足题意得方案数,设f(n)=\sum_{i\geq 0}^n\binom{n}{i}g(i)

f_{i,j}表示i子树内所有点颜色小于ji的色恰好为j的方案数,那么选出的颜色值域1...k可以不是连续的,就可以树上\rm dp了,然后前缀和优化即可。然后二项式反演求g即可

强大。

树上问题 组合计数 dp

2022.10.10补
上一篇 «
2022.10.3补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors