篮球比赛1(basketball1.*)
Czhou为了提高机房里各种神牛的身体素质，决定在每次训练后举行篮球比赛。为了保持比赛公平，Czhou要将神牛们分成两队。首先神牛们赛前都要排成固定的队伍；然后Czhou将队伍分成一半（前一半和后一半队伍人数可以不等），再分别从两个队伍中选出一些人进行篮球比赛。为了保持公平性，Czhou要求第一个队伍参加比赛的神牛能力的XOR值等于第二个队伍参加比赛的神牛能力的and值。为了增加比赛趣味，每次比赛的参加神牛们不能一样，Czhou现在想知道可以举办多少天的比赛。(很明显参加比赛的人数不能为0)
Xor即为亦或, 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1 , 1 xor 1 = 0。
And即为与, 0 and 0 = 0, 0 and 1 = 0, 1 and 0 = 0, 1 and 1 = 1。
举个例子10 and 2 = 10，10 xor 2 = 8， 10 = (1010)2 2 = (10)2 8 =(1000)2
Input:basketball1.in
第一行n，表示机房有n个神牛。
第二行有n个数a_i，表示各个神牛的能力值，并且这是赛前各个神牛的排队方式。
Output: basketball1.out
就一个数字，表示可以举办多少天比赛。由于天数会比较多，输出结果模1000000007。
Sample1.input:
3
1 2 3
Sample1.output
1
Sample2.input
4
1 2 3 3
Sample2.output
4
样例1说明：1 xor 2 = 3
样例2说明：可以举办四天比赛，参加比赛的双方队伍分别是（1,2）（3）；（1,2）（3）；(1,2)(3,3)；（3）（3）这里虽然能力值相同，但是指的是不同的牛。
对于(1,2)(3,3)来说，队伍分为两个队伍：(1,2)(3,3)，再从各自队伍选出全部选手参加比赛
对于（3）（3）来说，队列分为两个队伍：（1,2,3）(3)，再从各自队伍中选出3进行比赛
数据范围：
0<=n<=10^3
0 <= a_i <1024
一题DP，一开始卡在去重。。。应该还要写个快速读入的
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 const int mod=1000000007; 6 7 int n; 8 long long A[1001],XOR[1001][1024],AND[1001][1024],sum[1024]; 9 long long ans=0; 10 11 int main() 12 { 13 cin>>n; 14 for(int i=1;i<=n;i++) cin>>A[i]; 15 memset(sum,0,sizeof(sum)); 16 for(int i=1;i<n;i++) 17 { 18 for(int j=0;j<1024;j++) 19 { 20 XOR[i][j^A[i]]+=sum[j]; 21 XOR[i][j^A[i]]%=mod; 22 } 23 XOR[i][A[i]]++; 24 XOR[i][A[i]]%=mod; 25 for(int j=0;j<1024;j++) 26 { 27 sum[j]+=XOR[i][j]; 28 sum[j]%=mod; 29 } 30 } 31 memset(sum,0,sizeof(sum)); 32 for(int i=n;i>1;i--) 33 { 34 for(int j=0;j<1024;j++) 35 { 36 AND[i][j&A[i]]+=sum[j]; 37 AND[i][j&A[i]]%=mod; 38 } 39 AND[i][A[i]]++; 40 AND[i][A[i]]%=mod; 41 for(int j=0;j<1024;j++) 42 { 43 sum[j]+=AND[i][j]; 44 sum[j]%=mod; 45 } 46 } 47 memset(sum,0,sizeof(sum)); 48 for(int i=1;i<n;i++) 49 { 50 for(int j=0;j<1024;j++) 51 { 52 sum[j]+=XOR[i][j]; 53 sum[j]%=mod; 54 } 55 for(int j=0;j<1024;j++) 56 ans=(ans+sum[j]*AND[i+1][j])%mod; 57 } 58 cout<<ans<<endl; 59 }
原文：http://www.cnblogs.com/InWILL/p/5966109.html