2020-04-27 19:51 已编辑深圳大学 C++

关注

G NIM游戏

受一位神仙启发, 简述一下 $j$ $\color{Red}{iangly}$ 的做法 submit

$F_a = 1+bx^a$

所求即

$[x^0]IFWT\prod_{a} FWT(F_a)\\ = \sum_{k} \prod_{a} [x^k] FWT(F_a)\\ = \sum_{k} \prod_{a} \sum_{i} (-1)^{|i\&k|}f_i\\ = \sum_{k} \prod_{a} (1+(-1)^{|k\&a|}b)\\$

设 $h[k] = \prod_{a} (1+(-1)^{|k\&a|}b)$

发现可以类似FWT, 从低位到高位, 枚举01减少重复计算

即 $h[k][c] = \prod_{a} (1+(-1)^{|k\&a|+c}b)\ \ |\ c\in\{0,1\}$

转移 : 对于 $t=2^i$
$h[k][0] = h[k][0]*h[k+t][0]$
$h[k][1] = h[k][1]*h[k+t][1]$
$h[k+t][0] = h[k][0]*h[k+t][1]$
$h[k+t][1] = h[k][1]*h[k+t][0]$

全部评论

推荐最新楼层

Hs-Zzz

石家庄市第二中学 C++

神仙写的实在是太好了！

点赞回复分享

发布于 2020-09-18 11:55

Miichiru

楼主

深圳大学 C++

https://www.nowcoder.com/discuss/362922?type=101

点赞回复分享

发布于 2022-01-19 13:29

昨天 17:02

Fibocom广和通_助理工程师(准入职员工)

校招汇总-春招（五）

春招已经开始了，大家尽快投递！整理不易，更多春招开启的公司在下面专栏里面点赞收藏加评论，这是我更新的动力！！！感谢支持！！！更多专栏：超详细的嵌入式面经专栏（适用于小白学习和大佬复习）：https://www.nowcoder.com/creation/manager/columnDetail/mGYoDz25届春招公司大全专栏:https://www.nowcoder.com/creation/manager/columnDetail/0ybKdp26界小伙伴看过来，下面专栏包含26届实习和九月开启秋招和明年开启的春招公司合集26届校招汇总：https://www.nowcoder.com/...

投递奥马冰箱等公司9个岗位 > 校招岗位汇总

点赞评论收藏

02-11 16:36

华为_产品经理(准入职员工)

双非挂科本科挣扎签大厂全过程

本文仅支持富有一定理想、具备端正三观的学习工作者理性讨论。非装逼、非炫富、非卖弄、非歧视、非教育、非批判。昨天在与一名牛友深夜交流工作与学习，比较有感而发，为大家整理了我的经历，这里以时间顺序叙述，权当参考，坏处请大家避免、好处大家可以共同探讨。自我介绍一下：重庆邮电大学智能制造工程本科大四，目前在重庆大学国家卓越工程师学院学习。重庆邮电大学，绩点2.6，挂科3科，后补考过；重庆大学绩点3.7，年级前30%（均为北大4.0）。获省奖2项、校奖若干、一篇会议论文集，可检索；一专利。在海康实习后，后获得阳光电源、京东方等offer，已签华子，base20k。主要成就方向：机器视觉、机器人技术、计算...

下午吃泡馍：“不过没关系，工作压力、学习压力、经济压力、家庭压力不过尔尔。” 这是强者应有的姿态！祝百尺竿头更进一步！

牛客创作赏金赛

点赞评论收藏

01-07 07:54

已编辑

门头沟学院前端工程师

麦当劳毁意向

十二月份OC谈薪，接受以后表示在审批，一月份告知HC满了

后端彭于晏：以后只吃肯德基

点赞评论收藏

02-07 17:17

已编辑

淘天集团_后端开发(准入职员工)

双非本勇闯淘天

timeline：8.20 一志愿简历挂9.03 二志愿一面挂9.03 被捞简历又挂12.09 被捞12.11 一面12.13 二面12.16 hr面12.17 加面，入池1.3 被捞，主管面1.7 hr面1.10 oc终于等到你~出乎意料的给我这个双非本定了p5，这下真是淘孝子了#阿里##淘天##阿里求职进展汇总##秋招#

Astraia：双一流不是双非

阿里求职进展汇总

点赞评论收藏

02-11 15:40

已编辑

Fibocom广和通_助理工程师(准入职员工)

嵌入式操作系统（五）

目录：1.你了解IO模型吗？请你介绍一下？2.BIO、NIO有什么区别？3.Reactor、Proactor模式是什么？有什么区别？4.你了解socket中select、epoll吗？请你说说区别？5.linux零拷贝的原理？内容：1.你了解IO模型吗？请你介绍一下？阻塞IO：调用IO操作时，程序会阻塞（即等待），调用者期间什么 也不做，不停检查这个函数有没有返回，必须等待这个函数返回后才能进行下一个动作。但可能导致程序在等待IO操作时效率低下。非阻塞IO：IO操作会立即返回，如果数据不可用，程序会继续执行，不会等待。程序可以通过轮询来检查IO操作是否完成，但需要手动管理数据的状态和进程调度。...

嵌入式/C++八股

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 一人推荐一个值得去的通信/硬件公司 #

# 产品实习，你更倾向大公司or小公司 #

# 大学四年该怎么过，才不算浪费时间？ #