首页 > 其他 > 详细

【HDU5909】Tree Cutting

时间:2020-02-06 23:21:29      阅读:72      评论:0      收藏:0      [点我收藏+]

题目描述

题目大意:
给你一棵 $n$ 个节点的树,每个节点都有一个小于 $m$ 的权值
定义一棵子树的权值为所有节点的异或和,问权值为 $0..m−1$ 的所有子树的个数

题解

考虑 $dp$
设 $f_{i,j}$ 表示以 $i$ 为根节点的子树中,异或和为 $j$ 的子树的个数
那就直接用 $fwt$ 优化即可
具体就是一开始先 $fwt$ 好然后累乘,最后再 $fwt$ 回去

【HDU5909】Tree Cutting

原文:https://www.cnblogs.com/xjqxjq/p/12271037.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!