1 条题解
-
1
容易发现 ,从而可以认为 ,也即 。
如果 ,则 ,暴力做一次异或卷积即可。
即,求若干 的异或卷积,可以用 FWT 变成仅在 处权值非 。找到哪些数和所有给定数交均为偶数即可,而这个可以容斥计算贡献:给大小为 的子集 的贡献,则
使用高维前缀和即可做到 。
这样就可以求出 FWT 后的数组。最后 IFWT 回来时先不除 ,留到最后计算答案时再除。
对于 ,考虑枚举计算某 位之间的贡献。显然要 次枚举。
每次把枚举出来的位压缩成一个 进制数,求这 项的异或卷积即可。
由于枚举 位压缩后值域很小,暴力分类讨论 FWT 即可。
参考代码。
- 1
信息
- ID
- 3811
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 12
- 已通过
- 3
- 上传者