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; }

轉載于:https://www.cnblogs.com/372465774y/archive/2012/10/22/2734012.html

總結

以上是生活随笔為你收集整理的xmu 1254.异或求和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。