异或求和
Problem's Link: http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1254
Mean:
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
analyse:
看到这么大的输入，再看看时限是500ms，开始有点摸不着头脑，看来只能用log(n)的方法来做了。
典型的位运算题目。
首先我们求出[A,B]区间中所有数各个位上1的个数。比如[1~8]就是1,4,4,4；
怎么求呢？
我们可以打表找一下规律：
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
.....
我们会发现，[1,n]中第k位总共1的个数就是：n/(k<<1) *(k<<1 /2 )。或者说：符合 x mod 2^k >=2^（k-1） 的 x 第k位就是1。
额，这个要自己去找规律。
要求[A~B]区间内各位上1的个数，只需要B1[i]-A1[i]就行。
同理，我们可以求出[C~D]区间上各位1的个数。
剩下的就是怎么求和了。
求和比较简单：
区间【A,B】第k位为1的个数乘以区间【C,D】第k位为0的个数+区间【A,B】第k位为0的个数乘以区间【C,D】第k位为1的个数）*2^(k-1)。
Time complexity: O(logn)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-05-11.38
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
void get1( LL n , LL arr []) { /**< 求1~n所有数各个位上1的个数之和 */
for( int i = 1; i < 32; ++ i) arr [ i ] = 0;
for( LL i = 1 , f = 2 ,b = 1; b <=n; ++ i , f <<= 1 ,b <<= 1) {
arr [ i ] =(n / f) *( f / 2); /**< 对于每一位,1~n可分为n/t组(t是每组的01数量)，其中每组有t/2个是1 */
if(n % f >=b) arr [ i ] +=(n % f -b + 1); /**< 加上余数部分 */
}
}
int main() {
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL n , t;
cin >> t;
while( t --) {
LL A ,B , C , D , Mod , a1 [ 32 ], b1 [ 32 ], c1 [ 32 ], d1 [ 32 ];
cin >> A >>B >> C >> D >> Mod;
get1( A - 1 , a1); get1(B , b1); get1( C - 1 , c1); get1( D , d1);
LL ab1 [ 32 ], ab0 [ 32 ], cd1 [ 32 ], cd0 [ 32 ];
for( int i = 1; i < 32; ++ i) ab1 [ i ] = b1 [ i ] - a1 [ i ], cd1 [ i ] = d1 [ i ] - c1 [ i ];
int l1 =B - A + 1 , l2 = D - C + 1;
for( int i = 1; i < 32; ++ i) ab0 [ i ] = l1 - ab1 [ i ], cd0 [ i ] = l2 - cd1 [ i ];
LL sum = 0 , base = 1;
for( int i = 1; i < 32; ++ i)
sum =( sum +( base <<( i - 1)) % Mod *( ab0 [ i ] % Mod * cd1 [ i ] % Mod + ab1 [ i ] % Mod * cd0 [ i ] % Mod) % Mod) % Mod;
cout << sum << endl;
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-05-11.38
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
void get1( LL n , LL arr []) { /**< 求1~n所有数各个位上1的个数之和 */
for( int i = 1; i < 32; ++ i) arr [ i ] = 0;
for( LL i = 1 , f = 2 ,b = 1; b <=n; ++ i , f <<= 1 ,b <<= 1) {
arr [ i ] =(n / f) *( f / 2); /**< 对于每一位,1~n可分为n/t组(t是每组的01数量)，其中每组有t/2个是1 */
if(n % f >=b) arr [ i ] +=(n % f -b + 1); /**< 加上余数部分 */
}
}
int main() {
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL n , t;
cin >> t;
while( t --) {
LL A ,B , C , D , Mod , a1 [ 32 ], b1 [ 32 ], c1 [ 32 ], d1 [ 32 ];
cin >> A >>B >> C >> D >> Mod;
get1( A - 1 , a1); get1(B , b1); get1( C - 1 , c1); get1( D , d1);
LL ab1 [ 32 ], ab0 [ 32 ], cd1 [ 32 ], cd0 [ 32 ];
for( int i = 1; i < 32; ++ i) ab1 [ i ] = b1 [ i ] - a1 [ i ], cd1 [ i ] = d1 [ i ] - c1 [ i ];
int l1 =B - A + 1 , l2 = D - C + 1;
for( int i = 1; i < 32; ++ i) ab0 [ i ] = l1 - ab1 [ i ], cd0 [ i ] = l2 - cd1 [ i ];
LL sum = 0 , base = 1;
for( int i = 1; i < 32; ++ i)
sum =( sum +( base <<( i - 1)) % Mod *( ab0 [ i ] % Mod * cd1 [ i ] % Mod + ab1 [ i ] % Mod * cd0 [ i ] % Mod) % Mod) % Mod;
cout << sum << endl;
}
return 0;
}
/*
*/
