lowbit

树状数组(lowbit)

Time Limit:1000ms Memory Limit:128MB

题目描述

这天，LYK在学习树状数组。

当它遇到一个叫lowbit的函数时有点懵逼。lowbit(x)的意思是将x分解成二进制，它的值就是，其中k是最小的满足(x & )>0的数。（&是二进制中的and运算）

LYK甚至知道lowbit(x)=(x&-x)。但这并没什么用处。

现在LYK有了n个数字，为了使自己更好的理解lowbit是什么意思。它想对所有n^2个二元组求lowbit。具体的，对于一个二元组(ai,aj)，它的值为lowbit(ai xor aj) (xor表示异或的意思)，那么总共有n^2对二元组，LYK想知道所有二元组的值加起来是多少。

这个答案可能很大，你只需输出这个值对1000000007取模后的结果就可以了。

输入格式(lowbit.in)
第一行一个数n，表示有n个这样的数字。

第二行n个数ai。

输出格式(lowbit.out)

一个数表示答案。

输入样例

1 2 3 4 5

输出样例

数据范围

对于30%的数据n<=1000。

对于另外10%的数据ai<=1。

对于再另外10%的数据ai<=3。

对于再再另外20%的数据ai<1024。

对于100%的数据1<=n<=100000,0<=ai<2^30。

　　先说一下暴力的做法（只能拿70分）；

分类处理

　　对于前30%的数据，直接按照题目去做就行。

　　接下来40%的，a[i]范围较小，开一个桶数组，记录每个数出现了多少次（因为n<=100000,而a[i]<=1024,每个数一定出现过多次，我们只算一次就行了）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<math.h>
using namespace std;
#define M 1000000007
long long n,c;
int f[10205];
long long ans,o,maxn;
long long last=0,x,y,t;
long long     lowbit(long long x)
{
    return x&(-x);
} 
int main()
{
    freopen("lowbit.in","r",stdin);
    freopen("lowbit.out","w",stdout);
    scanf("%lld",&n);
    if(n<=1000) //这里掉了个等号，调了好久。。。。
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&f[i]);
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        o=lowbit((long long)f[i] ^ f[j]),ans=(ans+o)%M;
        ans=ans*2%M;
        cout<<ans;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&c);
        f[c]++;maxn=max(maxn,c);
    }    
    for(int i=0;i<=maxn;i++)
    for(int j=i+1;j<=maxn;j++)
    {        
        t=(i ^ j);
        o=lowbit(t);
        ans=(ans+o*f[i]*f[j]%M)%M;
    }
    ans=ans*2%M; 
    cout<<ans;
    return 0;
}

满分的做法就要考虑lowbit 和二进制数的性质了。

　　lowbit是指某数在二进制中最后一个“1”所在位置的权值。

　　两个数 xor（异或）的lowbit与他们从低位到高位第一个不同位的权值有关。

思路

　　(1)那么，我们就从低位向高位注意比较有多少个在这个位上是“1”，多少个是“0”。分别放在集合X,集合Y中。

　　(2)那么对于任意a∈X,b∈Y,, lowbit(a,b)就是这个位的权值。

　　这样集合X和Y之间的lowbit就求出来了（集合X，Y内部的数的lowbit还没求），接下来就分别对集合X，Y内部的数，对下一位进行同样操作 (1)(2）

实现的算法可以是分治，也可以是trie树。

　　分治做法代码：

#include<iostream>
#include<queue>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
#define M 1000000007
int a[100009],n;
int b[100009];
long long ans=0,t;
void work(int n,int t)
{
    if(n<=1||t>29)    return;
    int l=0;
    for(int i=1;i<=n;i++)
        if(a[i]&(1<<t))    b[++l]=a[i];
    int r=l;
    for(int i=1;i<=n;i++)
        if(!(a[i]&(1<<t)))    b[++r]=a[i];
    ans=(ans+(long long)(l*(r-l)*(1<<t)%M))%M;
    for(int i=1;i<=l;i++)    a[i]=b[i];
    work(l,t+1);
    for(int i=1;i<=r-l;i++)    a[i]=b[i+l];
    work(r-l,t+1);
}
int main()
{
    freopen("lowbit.in","r",stdin);
    freopen("lowbit.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    work(n,0);
    cout<<ans*2%M;
    return 0;
}

　　trie树：