Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


lowbit解题报告

题目描述

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

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

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

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

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


输入格式

第一行一个数n,表示有n个这样的数字。

第二行n个数ai。


输出格式

一个数表示答案。


数据范围

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

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

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

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

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

解题思路

这个题可以分治,把奇数和偶数分成两堆,然后就AC
思想就是转成二进制,然后异或,如果最末位相同,就向前搜寻,需要注意ans要开long long。
· 1.lowbit(x^y)=1, 把x和y分解成二进制,奇数的二进制末尾是1,偶数的二进制末尾是0,然后把奇数放到左边,偶数放到右边,那么有(奇数个数×偶数个数×2)对二元组,lowbit起来是1。
· 2.lowbit(x^y)=2, 奇数设有x个,偶数有y个,x、y全奇或全偶,若全奇,则二进制倒数第二位一个是0,一个是1
分治完以后,二元组一个在左边,另一个在右边,这样的贡献是很容易统计的。
对于每一个数他只在最多31层中被分治到,所以范围就是1~31,时间复杂度O(n×31)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#define P 1000000007
using namespace std;
int a[111111],b[111111];
long long ans;
void work(int p,int u)
{

if(p<=1||u>=30)
return ;
int l=0;
for(int i=1;i<=p;i++)
if(a[i]&(1<<u)) b[++l]=a[i];
int r=l;
for(int i=1;i<=p;i++)
if(!(a[i]&(1<<u))) b[++r]=a[i];
for(int i=1;i<=p;i++) a[i]=b[i];
ans+=((1ll*(1<<u))%P*l)%P*(p-l)%P;
work(l,u+1);
int q=0;
for (int i=l+1;i<=r;i++) a[++q]=a[i];
work(q,u+1);
}
int main()
{

freopen("lowbit.in","r",stdin);
freopen("lowbit.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
work(n,0);
printf("%lld",ans*2%P);
return 0;
}

Markdown

最近的文章

game解题报告

题目描述 游戏是一个在带权图G上进行的,N个点,M条边,边权c(e),点权w(v),G的点数有偶数个,规则如下;· 魅音和诗音分别将图中的点染色,诗音黑色,魅音蓝色,魅音先手· 一个点只能被染一次· 双方轮流选择点染色,一共选N/2轮,所有点都完成染色经过 N/2 轮游戏之后,两人都得到了一个顶点集 …

于  贪心 继续阅读
更早的文章

alien解题报告

题目描述 给你一个R*C的地图,现在其中某些点已经有障碍物了,现在有一个大小为A+B的飞船需要降落在地图中的某个位置,要求飞船降落区域没有障碍物,请问有多少种降落区域选择的方案? 输入格式 第一行是四个整数,R C P Q接下来的P 行每行两个整数x,y表示(x,y)这个点为障碍物接下来的Q行每 …

于  前缀和 继续阅读