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]$

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

全部评论

(2) 回帖

加载中...

话题同步到我的动态回帖

返回全部帖子

本文相关内容

等你来战

查看全部

牛客练习赛124_PLUS

报名截止时间：2024-04-26 22:00
大连大学2024年4月程序设计竞赛（同步赛）

报名截止时间：2024-04-27 21:00
牛客小白月赛92

报名截止时间：2024-04-28 21:00
武汉工程大学第六届ACM程序设计竞赛（同步赛）

报名截止时间：2024-04-29 16:00
2024牛客五一集训派对day1

报名截止时间：2024-05-01 17:00
2024牛客五一集训派对day2

报名截止时间：2024-05-02 17:00
2024牛客五一集训派对day3

报名截止时间：2024-05-03 17:00
2024牛客五一集训派对day4

报名截止时间：2024-05-04 17:00
2024牛客五一集训派对day5

报名截止时间：2024-05-05 17:00
牛客周赛 Round 41

报名截止时间：2024-05-05 21:00
哈尔滨华德学院第十五届程序设计竞赛（同步赛）

报名截止时间：2024-05-11 16:00
第四届上海理工大学程序设计全国挑战赛

报名截止时间：2024-05-12 17:00
牛客周赛 Round 42

报名截止时间：2024-05-12 21:00

G NIM游戏

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐