首页 > 其他 > 详细

对子集卷积的一些思考

时间:2020-05-26 09:08:01      阅读:67      评论:0      收藏:0      [点我收藏+]

首先我们要知道 集合占位幂级数:将原始数组的第i个值放在第bitcount(i)行上,此时一维数组就变为二维数组。相关内容可

看下2015年吕凯风的论文。

对于子集卷积,它的正确性在于bitcount(i)+bitcount(j)>=bitcount(i | j),因此如果bitcount(i)+bitcount(j)==bitcount(i | j),它一定会是我们要统计的答案。对于位数大于其的答案,我们将其舍去。

若多项式的乘法为子集卷积意义,那么就相当于对于 每一列 进行普通的多项式操作。目前理由不明。或许是乘法的正确性?

因此,要实现某些多项式操作,就需要有相应的递推。当然,此时平方复杂度的递推不失为一个不错的选择。

对子集卷积的一些思考

原文:https://www.cnblogs.com/GreenDuck/p/12963040.html

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