A Bit Fun
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1104 Accepted Submission(s): 623
Problem Description
There are n numbers in a array, as a0, a1 ... , an-1, and another number m. We define a function f(i, j) = ai|ai+1|ai+2| ... | aj . Where "|" is the bit-OR
operation. (i <= j)
The problem is really simple: please count the number of different pairs of (i, j) where f(i, j) < m.
operation. (i <= j)
The problem is really simple: please count the number of different pairs of (i, j) where f(i, j) < m.
Input
The first line has a number T (T <= 50) , indicating the number of test cases.
For each test case, first line contains two numbers n and m.(1 <= n <= 100000, 1 <= m <= 230) Then n numbers come in the second line which is the array a, where 1 <= ai <= 230.
For each test case, first line contains two numbers n and m.(1 <= n <= 100000, 1 <= m <= 230) Then n numbers come in the second line which is the array a, where 1 <= ai <= 230.
Output
For every case, you should output "Case #t: " at first, without quotes. The
t is the case number starting from 1.
Then follows the answer.
t is the case number starting from 1.
Then follows the answer.
Sample Input
2 3 6 1 3 5 2 4 5 4
Sample Output
Case #1: 4 Case #2: 0
Source
Recommend
liuyiding
题意：
给你n个数字。问你有多少i,j.组合使得。a[i] | a[i+1] | a[i+2].......|a[j]的值小于m.i<=j。
思路：
对于|运算。很简单。但对于逆运算就不好想了。由于|运算只增不减。单调性可以利用。如果f(i,j)>=m了。那i和j以后的f值肯定>=m了。这样就可以用排除法做了。我们可以维护一个数组。存二进制中对应位1的个数。这样删除前面的数就好办了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
int bit[35],abit[35];
int a[maxn];
int main()
{
int i,j,k,n,m,sum,pre,t,cas=1;
__int64 ans;
bit[0]=1;
for(i=1;i<=31;i++)//预处理出二进制数组
bit[i]=bit[i-1]<<1;
scanf("%d",&t);
while(t--)
{
sum=0;
memset(abit,0,sizeof abit);//记录各二进制位1的个数
scanf("%d%d",&n,&m);
ans=(__int64)n*(n+1)/2;//用排除法。所以先算出总组合数。(n*(n-1))/2 + n。
for(i=0;i<n;i++)
scanf("%d",a+i);
i=j=0;//i,j指针扫一遍
while(j<n)
{
while(sum<m&&j<n)//如果小于m。可以向右扩展。
{
sum|=a[j];
for(k=0;k<31;k++)
if(a[j]&bit[k])
abit[k]++;
j++;
}
pre=i;
while(sum>=m)
{
for(k=0;k<31;k++)
if(a[i]&bit[k])
abit[k]--;
sum=0;
for(k=0;k<31;k++)
if(abit[k])
sum|=bit[k];
i++;
}
ans-=(i-pre)*(n-j+1);//(i-pre)的部分和(n-j+1)的部分肯定不能组合。
}
printf("Case #%d: %I64d\n",cas++,ans);
}
return 0;
}