欢迎光临散文网会员登陆 & 注册

[ABC281G] Farthest City

2023-03-31 14:34 作者:BNU_ACM 0人读过 | 我要投稿

从拓扑序的角度去做状态转移
对以下因素应用乘法原理可得一次状态的转移系数

从剩下的点（排除1和N）中选k个作为拓扑序下一层的选法，即组合数
新层的k个数之间的连接关系可能性，pow(2, k*(k-1)/2)，潜在边集的幂集的势
新层与上一层的连接关系，为pow(上一层点的非空子集的个数, k)

状态的定义有多种；
可预处理出重复使用的中间值

标签：

[ABC281G] Farthest City的评论 (共条)