[JZOJ4937] 与运算

Description

Solution

设F[i]表示当前前若干项异或起来为i的最大答案

考虑转移。
显然我们可以只转移i的一个二进制位。

找一位去掉，设去掉后为j，并求出有多少个a能包含j而不包含i（包含指i的所有1的位在这些a上对应的位也是1）

设num[i]表示有多少个包含i的。
显然包含j一定包含i
因此求的值就是num[j]−num[i]

然后直接转移即可。

关键在于预处理num
直接递推会有重复，怎么办呢。
观察特性
0~2m−1处理
可以分成[0~2m−1−1],[2m−1~2m−1]两部分，前一部分2m−1这一位是0，后一部分这一位是1。

所以显然后一部分每一个的num[i]可以转移到前一个的num[i−2m−1]中。

然后其他的m<script type="math/tex" id="MathJax-Element-3542">m</script>也类似，可以用分治的办法在两个区间分别下去。
为了避免重复，返回的时候再转移。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 1000005
#define M 1048576
#define LL long long
using namespace std;
int n;
LL a[N],num[M+5],f[M+5],lim;
void fd(LL l,LL r,LL c)
{
    LL mid=1<<(c-1);
    if(l>=r-1) return;
    fd(mid+l,r,c-1);
    fd(l,l+mid,c-1);
    fo(i,0,mid-1) num[l+i]+=num[l+i+mid];
}
int main()
{
    cin>>n;
    memset(num,0,sizeof(num));
    fo(i,1,n) scanf("%lld",&a[i]),num[a[i]]++,lim=max(lim,a[i]);
    fd(0,lim,20);
    LL ans=0;
    fod(i,min(2*lim,(LL)M),1)
    {
        fo(j,0,19)
        {
            LL p=1<<j;
            if((i&p)>0) f[i-p]=max(f[i-p],f[i]+((LL)i-p)*(num[i-p]-num[i]));
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
}