首页 > Web开发 > 详细

[BZOJ3696][FJSC2014]化合物(异或规则下的母函数)

时间:2015-03-28 23:07:08      阅读:433      评论:0      收藏:0      [点我收藏+]

题目:http://hzwer.com/3708.html

分析:

类似树分治思想,设f[x][i]表示以x为根的子树的所有点中,与x的距离为i的点有多少个,这个可以预处理出来

然后我们考虑每颗子树对ans的贡献

1、以x为起点的某条链i,ans+=f[x][i]

2、以x为起点的两颗不同的子树i,j:

    如果把“异或”看作“和”,那么就是两个子树对应的f[]相乘(其实就是母函数啦)

    但是这里是“异或”啊!!其实只要把作乘法时候的系数不要变,指数xor一下就行

    比如说正常的乘法:{1,3}*{1}==(x+3x^2)*(x)==x^2+3x^3

    这里就是{1,3}^{1}==(x+3x^2)^(x)==x^(1^1)+3x^(1^2)==x^0+3x^3

[BZOJ3696][FJSC2014]化合物(异或规则下的母函数)

原文:http://www.cnblogs.com/wmrv587/p/4374898.html

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