HUSTOJ discuss3

Problem1151--#6026. 「by hzq84621」集合

1151: #6026. 「by hzq84621」集合

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

对于一个非空集合 ${a_i\}$ ，我们称一个集合是 magical 的，当且仅当它满足以下两个条件。

$a_{1} & a_{2} & \dots & a_{n} = 0$ （ $&\&$ 表示按位与）；
${a_i}$ 的任意一个非空真子集不满足 (1)。

小 A 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。

小 A 现在想要知道这个集合的 magical 的非空子集数量是多少。
为了防止不必要的麻烦，请将答案模 $10^9+7$ 后输出。

第一行一个整数 $T$ 表示数据组数。
接下来每组数据第一行一个整数 $n$ ，表示集合元素数量。
第二行 $n$ 个整数，表示这个集合中的元素。

输出共 $T$ 行，每行对应这组数据的答案。

样例输入 1

1
5
0 1 2 4 4

样例输出 1

样例解释 1

$6$ 个 magical 的集合是 ${0\},\{1,2\},\{1,4\},\{1,4\},\{2,4\},\{2,4\}$ 。

样例输入 2

30
30
28 11 8 96 92 16 114 126 47 77 82 88 120 46 56 74 113 23 72 126 109 26 24 62 96 110 89 6 32 28 
30
58 94 109 124 9 102 48 96 27 51 0 15 111 89 106 117 14 73 114 24 53 94 85 78 54 50 17 46 28 54 
30
39 68 14 2 32 9 118 105 78 17 98 81 84 7 42 65 105 87 83 60 88 42 51 78 75 23 86 100 74 23 
30
33 97 127 58 53 109 60 25 22 16 63 12 13 1 52 29 74 56 123 60 78 74 44 52 8 118 88 93 62 123 
30
18 19 47 45 46 104 119 72 73 22 50 4 10 56 100 106 38 57 25 101 42 12 72 28 117 29 125 127 3 8 
30
55 32 114 10 15 69 62 52 27 59 80 103 18 109 55 124 49 53 53 67 93 113 125 47 9 90 59 79 90 17 
30
85 0 9 123 112 98 10 79 55 8 107 109 87 116 126 114 78 66 58 9 102 35 95 4 124 13 89 43 6 49 
30
103 83 85 46 124 51 23 4 102 116 31 75 45 7 105 37 62 59 88 113 72 15 67 65 103 68 48 14 0 55 
30
95 43 108 110 11 120 88 113 108 88 107 91 0 101 42 48 11 98 25 113 93 112 35 110 83 5 60 92 32 27 
30
69 39 77 37 48 10 127 71 100 92 121 70 99 45 97 62 42 17 71 19 89 60 99 41 19 79 30 88 40 114 
30
85 26 113 35 89 7 124 77 58 4 105 29 69 55 20 17 75 62 117 82 36 32 68 67 116 3 96 90 45 32 
30
113 47 85 117 76 82 10 57 24 98 67 21 47 91 88 17 71 48 69 77 82 26 43 113 35 47 23 102 81 54 
30
7 71 96 58 42 18 30 93 104 36 76 111 34 100 126 63 59 62 69 49 87 83 10 17 98 110 61 39 85 58 
30
48 12 52 51 61 60 91 91 47 107 123 46 96 29 96 87 30 113 117 36 83 61 9 56 101 96 83 0 92 84 
30
52 104 67 3 61 78 80 92 113 54 71 37 76 64 27 19 4 88 86 24 14 45 60 124 100 100 43 47 6 13 
30
70 94 62 86 83 68 41 126 96 67 115 13 45 51 98 67 70 122 22 78 112 92 15 64 70 21 111 63 36 37 
30
1 126 68 108 123 109 39 118 0 45 55 24 105 71 42 60 69 29 41 121 30 33 50 103 127 68 59 49 50 50 
30
24 107 78 60 30 38 114 21 9 66 75 66 27 4 92 76 6 104 126 56 12 57 37 56 101 94 102 35 97 119 
30
54 35 78 41 117 46 28 53 43 55 63 80 17 37 85 47 83 4 9 97 20 122 55 97 50 125 81 108 76 68 
30
1 16 2 123 15 6 124 59 6 65 46 57 18 71 90 62 45 64 86 87 122 76 15 77 113 26 78 87 61 55 
30
58 15 98 35 31 35 35 42 109 77 35 113 4 5 74 80 46 117 106 95 109 45 35 84 120 24 4 12 0 46 
30
114 103 55 108 78 89 19 1 82 62 79 75 60 110 52 1 47 18 22 50 86 54 33 110 74 31 86 67 54 94 
30
80 107 57 37 76 67 11 90 104 127 100 106 43 28 25 96 70 23 8 54 25 93 55 106 121 2 56 85 49 53 
30
80 57 70 116 88 25 0 124 98 77 37 4 32 85 8 42 2 110 66 46 31 99 64 94 86 38 126 81 53 31 
30
17 88 25 68 107 50 23 106 91 127 27 90 83 119 79 40 110 92 63 64 49 45 58 66 18 29 123 16 54 68 
30
9 37 127 19 91 40 70 13 64 64 101 52 126 43 121 66 57 10 102 26 23 127 27 126 34 122 23 2 110 80 
30
43 65 123 14 2 78 92 12 96 110 25 69 39 4 83 101 31 76 38 36 118 76 84 83 6 8 31 52 87 118 
30
118 15 101 49 84 2 35 113 102 25 63 59 108 31 40 85 97 51 78 125 94 30 41 90 60 99 124 51 121 24 
30
91 95 92 117 107 125 92 43 105 101 63 118 109 94 127 118 112 17 113 59 12 61 40 31 4 45 24 88 4 103 
30
119 77 42 39 105 41 68 11 91 46 92 16 47 77 114 61 26 115 8 30 75 37 100 116 78 79 17 43 47 89

样例输出 2

对于前 $10%10\%$ 的数据， $n≤20n\leq 20$ ；
对于前 $30%30\%$ 的数据， $n≤30n\leq 30$ ；
对于前 $60%60\%$ 的数据， $0≤ai<128,T=10\leq a_i<128,T=1$ ；
对于前 $80%80\%$ 的数据， $0≤ai<256,T≤50\leq a_i<256,T\leq 5$ ；
对于前 $100%100\%$ 的数据， $T≤30,n≤100,0≤ai<512T\leq 30,n\leq 100,0\leq a_i<512$ 。

据说此题是埃及信息竞赛题。

Source/Category

[Submit] [Status]