day5上午——位运算

正睿青岛

对2^20次方取模，可以首先让它自然溢出（%2^32）,然后 &((1<<20) - 1)就是答案。

原码：00001
反码：11110
补码：11111 （反码+1，或者2^32-原来的数字）

__builtin_popcount(x)
__builtin_popcountll(x) x是long long，或者unsigned long long
_parity(x) 判x二进制下1个个数。（__builtin_popcount(x) & 1）
_ctz(x) x后面0的个数。_ctzll
_clz(x) x前面0的个数。_clzll
$\lfloor log_2x \rfloor = 32 - \_clz$(x)
手写：打一个0~2^16的表，计算里面多少个1，然后一个int按前面16位和后面16位的来算。

某个题

x^3x=2x
x^2x=3x

a+b = a^b + ((a&b)<<1)
a^b不进位，((a&b)<<1)进位后的。
所以a^b <= a+b
如果让a^b=a+b，那么((a&b)<<1)要是0.
(x&(2x))<<1是0，就是没有相邻的1。
然后计算多少x满足没有相邻的1。
f[i]表示到第i位，的方案数，f[i]=f[i-1]+f[i-2]。就是看第i位是不是1。

BZOJ 3329: Xorequ

枚举子集

子集dp。

for (int x=S; x; x=(x-1)&S); // 不能枚举到空集。
while (1) {
    //...
    if (x == 0) break;
    x = (x - 1) & S;
}
//按从大到小的顺序遍历。
//如果找S最大的子集，不能直接这样算。x必须是S的子集才是有效的。

吉夫特

枚举子集，转移。
优化：
当前O(1)修改dp，O(2^n)枚举子集。维护dp。
或者O(2^n)修改，O(1)转移，维护转移数组。

折半$s[i][j] = ∑_ka[i + 2^j + k]$

https://goaway.blog.luogu.org/solution-p3773

NOI 2014 起床困难症

bzoj 4245

一道数位dp题

查子集的个数，n<=60

void query(int l,int r,int L,int R) { // L,R查询区间，l,r线段树的区间l=0,r=2^60 
    if (L <= l && r <= R) {
        // 此时是固定了一段前缀，后面随便选。
        // 线段树区间是 [101... ~ 101111]，固定的前缀是101
        // 判断前缀是不是子集。 
    }
}

或的单调性

求多少区间的或不同。（st表可以求或的和）
l往后，看有没有31个数字分别有没有。倒着for一遍。pos[i]第i位，往右第一次出现的位置。倒着扫的过程。

或-> gcd。
st表求gcd。然后二分断点。（每次gcd只会变小，最多变小log次。所以断点右log个。二分断点。）

异或排序

求多少S，满足S<=2^60，S^A[i-1] <= S^A[i]。
为了让所有的A[i]都满足，所以分别考虑每个对相邻的数。
A[i] ^ S <= A[i + 1] ^ S
如果A[i]和A[i+1]的相同的位，那么可以不用考虑了，找到它们第一个不同的位置，它限制了S的这个位置必须是多少。

五维数点

f1[i]第一维小于i的集合。
f2[i]第二维..
f3, f4, f5

询问A,B,C,D,E
ans = f1[A] & f2[B] & f3[C] & f4[D] & f5[E]
空间复杂度O(kn^2/32)。
分块打表：$f1[\sqrt n]$， $f1[2\sqrt n]$， $f1[3\sqrt n]...$，$f1[\sqrt n\sqrt n]$
每次找到最近的$k\sqrt n$，然后暴力加入剩下的。
复杂度：$O(kn\sqrt n/32)$

bitset做匹配

没有通配符：
pos[a] = 101001001 a在A串的位置集合。
pos[b] = 010100000 b在A串的位置集合。
pos[c] =
pos[d] =
pos[e] =

B串为bcd的话，就是求pos[b] & (pos[c] >> 1) & (pos[d] >> 2)
修改一个位置，pos中修改两个值。
l~r中的串，& l~r

有通配符for的时候直接跳过。

bzoj 两个串。

bool矩阵乘法

bitset优化至$O(n^3/32)$

01卷积。
bitset可以知道哪一项让他变成非0了，而FFT不能。
FFT做：FFT的log的三次。
bitset：$n^2 / 32$

xor的和

枚举每一位的贡献。
这一位1的，和0的可以组合起来。

和的xor

sum(a[i] + a[j]) 的xor和。
每一位分别考虑，看第k位1的个数。就是(a[i] + a[j]) 在$2^k ... 2^{k+1}-1$的个数