ABC291G 题解

SMT0x400 · 2023-03-01 20:14:39 · 题解

ABC291G OR Sum

题意：有两个长度为 N 的序列 A,B，可以给 A 序列向左循环移动若干位，求 \sum (A_i|B_i) 的最大值。N\le 5\times 10^5 而 0\le A_i,B_i\le 31。

题解：发现 or 操作有点点困难，那么我们就把两个序列取反，然后求 and 的最小值。

尝试形式化枚举每个移动数量的过程，比如枚举一个移位 j，再枚举一个 i 计算答案。

这种位数特别少的题，就先枚举二进制位 k，对于每一位分别处理。设 a,b 分别为序列 A,B 的第 k 位取反。

然后就是两个 0/1 序列合并操作，我们需要求出一个答案数组 c，c_j=\sum a_i\times b_{(i+j)\% n}。

我们可以把 b 复制一遍，去掉取模 n，问题就变成了求 c_j=\sum a_i\times b_{i+j}。

这个形式还不是我们熟悉的形式，我们应该熟悉的形式是 c_{i+j}=\sum a_i\times b_j。

怎么办呢？拿 k 替换 (i+j)，问题就变成了 c_{k-i}=\sum a_i\times b_k。

左边式子 i 符号负的不好看，问题就变成了 c_{k+i}=\sum a_{-i}\times b_k。

右边下标为负数的很不好看，因为我们需要存储 a 数组，所以把 a 数组反转得到 a' 了，就是原来的存储 a_{-i} 的数组右移 n-1 位。

令 p=n-1-i，原式= c_{k+p}=\sum a'_{p}\times b_k。由上可知，多项式实际的值只有 [n-1,2n-2] 的这 n 位才有效。

发现就是多项式的形式，直接卷积即可。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
typedef int I;
I main(){I n;
    scanf("%d",&n);
    vector<I>a(n),b(n),c(n),d(n<<1),e,f(n);
    for(I i=0;i<n;++i)scanf("%d",&a[i]);
    for(I i=0;i<n;++i)scanf("%d",&b[i]);
    for(I k=0;k<5;++k){
        for(I i=0;i<n;++i)d[i]=(~b[i]>>k)&1,d[i+n]=d[i],c[n-1-i]=(~a[i]>>k)&1;
        e=atcoder::convolution(c,d);
        for(I i=0;i<n;++i)f[i]+=(n-e[i+n-1])<<k;}
    printf("%d\n",*max_element(f.begin(),f.end()));
    return 0;
}