引言
首杀，我的首杀……qwq
原来差点就 F 一血了……我 19:08:01 就提交了……8 min 就打完了……
结果 F 题让我发现我一直的异或卷积板子是假的……而且在平时只有一次卷积时可以证明不可能出锅……因为我最后一步的乘法打成加法了，然后平时这一位只可能是 000，0+0=0×00+0=
展开全文
F 题解
先 FWT，然后上猫树，在预处理之后全 FWT 回来，预处理复杂度是 nVlognlogVnV\log n\log VnVlognlogV 的。
查询只要求 (A∗B)[s](A*B)[s](A∗B)[s]，可以 O(qv)O(qv)O(qv) 求。
感谢牛客神机：此题可暴力FWT通过：
以下为做法：
1.枚举lll，递增rrr，跑的时候把fwtfwtfwt数组乘起来：O(n⋅n2∗1024)≈1e9O(\frac{n \cdot n}{2}*1024)\approx1e9O(2n⋅n∗1024)≈1e9
2.到有询问的lll，rrr，ifwt
展开全文
不会猫树qwq
提供一个分块思路吧。设块大小为BBB，记m=1024m = 1024m=1024
观察到复杂度要偏向预处理，考虑维护区间FWTFWTFWT点积，询问时再IFWTIFWTIFWT。
块内直接每个区间求出来，O(nBB2)=O(nBm)O(\dfrac nB B^2) = O(nBm)O
展开全文
首先对所有的位置 FWT 喵，记前缀非 0 积和 0 个数喵，这样就可以 处理区间积喵～然后我们其实不需要逆 FWT喵～，我们只需要用逆 FWT 的定义求一个点的值即可喵，时间复杂度少一个 log 喵～
时间复杂度 喵～
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
