xmu 1254.异或求和

1254.异或求和

Time Limit: 1000 MS Memory Limit: 65536 K
Total Submissions: 52 (19 users) Accepted: 13 (7 users)

Description

给你2个区间[A,B]和[C,D],现在只要求你求出区间[A,B]和[C,D]内任意2个整数异或后的和，因为答案可能会很大，你只需将结果%mod即可。

For(i:A→B)
For(j:C→D)
Sum += (i^j);

Input

输入第一行为T(T<=15),表示测试的数据组数，第2行到T+1行，每行5个数字，分别为A,B,C,D,mod(1<=A,B,C,D<2^31,A<=B,C<=D,1<=mod& lt;=1,000,000,007),即为上述的数值。

Output

输出有T行，每行有一个数字，代表题述的答案（即Sum % mod）。

Sample Input

3
5 11 9 12 43
9 12 5 11 83
1 1 2 2 3

Sample Output

18
24
0

//这题是我无意间看到的、不会做，然后也没找到题解，就把题目发到 ACMDIY群面
//然后晚上群里一位上海交大的童鞋给了我思路
//就是把每个数看成二进制数 求区间里面 第k位1有几个
比如 区间 【1,8】 那么 区间里面第一位是1的有4个 第二位 是1的4个 第3位是1个是4个 第4位是1的有1个
（只要把这8个数写成二进制，就可以看出来）
当时我也想过这样、问题是我求不来区间里面这些数中有几个第k位是1
然后他告诉我 符合 x mod 2^k >=2^（k-1） 的 x 第k位就是1
这样只要求出 x某个范围 ，其它就是它的等价类了

这样就可以很快求出 区间【1，N】里面 第k位是1个数 （1<=k<=31）
那么区间【A,B】里面第k位是1的个数就有了
然后 就是怎么求和了

求和比较简单 就是 ：
（区间【A,B】第k位为1的个数乘以区间【C,D】第k位为0的个数+区间【A,B】第k位为0的个数乘以区间【C,D】第k位为1的个数）*2^(k-1)

#include <iostream>
#include <map>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define __int64 long long
struct node
{
    __int64 rc[32][2];
};
void get1(__int64 n,node *R)
{
    int i;
    __int64 t=4,p=2;
    R->rc[1][1]=n/2;
    if(n%2) R->rc[1][1]++;
    for(i=2;p<=n;t=(t<<1))
    {
        R->rc[i][1]=(n/t)*(t-p);
        if(n%t>=p)   R->rc[i][1]+=(n%t-p+1);
        i++;
        p=(p<<1);
    }

}
int main()
{
    node a,b,c,d;
    int A,B,C,D;
    int Mod,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d %d %d",&A,&B,&C,&D,&Mod);
        memset(a.rc,0,sizeof(a.rc));
        memset(b.rc,0,sizeof(b.rc));
        memset(c.rc,0,sizeof(c.rc));
        memset(d.rc,0,sizeof(d.rc));
        get1(A-1,&a);
        get1(B,&b);
        int i;
        for(i=1;i<=31;i++)
         a.rc[i][1]=b.rc[i][1]-a.rc[i][1];
        __int64 len=(B-A+1);
        for(i=1;i<=31;i++)
         a.rc[i][0]=len-a.rc[i][1];
        get1(C-1,&c);
        get1(D,&d);
        for(i=1;i<=31;i++)
         c.rc[i][1]=d.rc[i][1]-c.rc[i][1];
        len=(D-C+1);
        for(i=1;i<=31;i++)
         c.rc[i][0]=len-c.rc[i][1];
         __int64 sum=0,m=1;
        for(i=1;i<=31;i++)
        {
     sum=(sum+(m<<(i-1))%Mod*(a.rc[i][0]%Mod*c.rc[i][1]%Mod+a.rc[i][1]%Mod*c.rc[i][0]%Mod)%Mod)%Mod;
        }
        Mod=(int)sum;
        printf("%d\n",Mod);
    }
    return 0;
}