【NOIP模拟赛】篮球比赛1

2014年11月5日1,1310

    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

题解

实际上是前几天模拟赛的一道题,只不过不需要高精了

暴力30分把子序列搜索出来然后枚举断点。。。

发现异或以及和运算都可以dp出来,注意和应该从f[i][j]->f[i+1][j&x]

f[i][j]表示前i个数集合异或值为j,且i在集合中的方案,注意前缀和运用 g[i][j]表示后i个…………和…………

统计答案过程略