解题思路
先把式子按二进制位拆开看。
设当前考虑第 k 位，权值为 2k。
由于按位与、按位异或、按位或都是“逐位独立”计算的，所以这一位对总答案的贡献，只和：
- ai 的第 k 位是 0 还是 1
- si 的类型
P4693.第3题-位运算权值
题目内容
天才同学给笨蛋同学留下一道小练习：给定一个长度为 n 的整数序列 {a1,a2,…,an}，以及一个同样长度为 n 的字符串 s，其中每个字符si 只可能是 1,2,3之一。
你需要在区间 [1,r]中选择一个整数 x，并据此计算这个序列的"权值和"。对每个位置i：
- 当 si=1时，该项贡献为 ai&x
- 当si=2时，该项贡献为 ai⊕x
- 当 si=3时，该项贡献为 ai∣x
定义总权值为：
W(x)=∑i=1nf(ai,x,si)
请你求出 maxx∈[1,r]W(x) 的值。
符号⊕表示按位异或运算(对两个数的二进制逐位异或)对应位不同为1，相同为0。例如5(1012)与3(0112)满足5 xor 3=6(1102)。
符号&表示按位与运算(对两个数的二进制逐位相与)对应位都为1时结果为1，否则为0。例如5(1012)与3(0112)满足5 and 3=1(0012)
符号∣表示按位或运算(对两个数的二进制逐位相或)对应位只要有一个为1结果为1，否则为0。
例如5(1012)与3(0112)满足5 or 3=7(1112)
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数t(1≤t≤2×105)代表数据组数，每组测试数据描述如下
第一行输入两个整数n和r(1≤n≤2×105;1≤r≤109)。
第二行输入n个整数a1,a2,...,an(0≤ai≤109)
第三行输入一个长度为n的字符串s，保证对所有1≤i≤n，都有si∈{1,2,3}
除此之外，保证单个测试文件的∑n不超过4×105
输出描述
对于每一组测试数据，新起一行输出一个整数，表示maxx∈[1,r]W(x)
样例1
输入
3
3 7
1 2 3
123
4 3
1 1 1 1
1111
5 10
5 6 7 8 9
23231
输出
15
4
60
说明
数组为 {2,2,3,3,2}。所有满足i=j的有序二元组 (i,j) 共有 5×4=20 个。其中满足 ai+aj 为合数的二元组有：
- ai=2,aj=2：和为 2+2=4（合数）。由于数组中有 3个 2，可以组成3×2=6 个这样的有序对。
- ai=3,aj=3：和为 3+3=6（合数）。由于数组中有2 个3，可以组成 2×1=2个这样的有序对。
总计 6+2=8个。
