农业公园网站建设,电子商务网站建立,大连响应式网站建设,node.js做网站传送门 我们要求的是\([x^0]\prod\limits_{i1}^n (2x^{a_i}1)\)#xff0c;其中乘积定义为集合对称差卷积。 这个直接做复杂度太高了#xff0c;考虑优化。注意到在FWT之后#xff0c;每一个序列中的值要么是\(3\)#xff0c;要么是\(-1\)#xff0c;而且这个只跟\(a_i\)有…传送门 我们要求的是\([x^0]\prod\limits_{i1}^n (2x^{a_i}1)\)其中乘积定义为集合对称差卷积。 这个直接做复杂度太高了考虑优化。注意到在FWT之后每一个序列中的值要么是\(3\)要么是\(-1\)而且这个只跟\(a_i\)有关。如果我们能够计算出每一个位置的\(3\)和\(-1\)的数量就可以IFWT然后求解。 那么我们不妨对于所有\(x^{a_i}\)加和然后做一遍对称差卷积。值得注意的事情是和的FWT等于FWT的和所以最后得到的每一位的结果就是“所有在FWT后当前位置为\(3\)的数组的个数-所有在FWT后当前位置为\(-1\)的数组的个数”。我们有可以知道这两者的和为\(N\)就可以快速计算出\(3\)和\(-1\)的数量。 强化版Global Round 2 H 代码 转载于:https://www.cnblogs.com/Itst/p/11173035.html
