Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-数组分割
题目 3171:

蓝桥杯2023年第十四届省赛真题-数组分割

时间限制: 2s 内存限制: 576MB 提交: 4171 解决: 868

题目描述

小蓝有一个长度为 N 的数组 A = [A0, A1,..., AN−1]。现在小蓝想要从 A 对应的数组下标所构成的集合 I = {0, 1, 2, . . . , N − 1} 中找出一个子集 R1，那么 R1在 I 中的补集为 R2。记 S1=∑r∈R1Ar，S2 =∑r∈R2Ar，我们要求 S1 和 S2 均为偶数，请问在这种情况下共有多少种不同的 R1。当 R1 或 R2 为空集时我们将 S1 或 S2 视为 0。

输入格式

第一行一个整数 T，表示有 T 组数据。
接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N，表示数组 A 的长度；第二行输入 N 个整数从左至右依次为 A0, A1, . . . , AN−1，相邻元素之间用空格分隔。

输出格式

对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对1000000007 进行取模后输出。

样例输入

2
2
6 6
2
1 6

样例输出

4
0

提示

对于第一组数据，答案为 4。（注意：大括号内的数字表示元素在数组中的下标。）
R1 = {0}, R2 = {1}；此时 S1 = A0 = 6 为偶数, S2 = A1 = 6 为偶数。
R1 = {1}, R2 = {0}；此时 S1 = A1 = 6 为偶数, S2 = A0 = 6 为偶数。
R1 = {0, 1}, R2 = {}；此时 S1 = A0 + A1 = 12 为偶数, S2 = 0 为偶数。
R1 = {}, R2 = {0, 1}；此时 S1 = 0 为偶数, S2 = A0 + A1 = 12 为偶数。

对于第二组数据，无论怎么选择，都不满足条件，所以答案为 0。


对于 20% 的评测用例，1 ≤ N ≤ 10。
对于 40% 的评测用例，1 ≤ N ≤ 102。
对于 100% 的评测用例，1 ≤ T ≤ 10, 1 ≤ N ≤ 103 , 0 ≤ Ai ≤ 109。


标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
蓝桥杯2023年第十四届省赛真题-平方差
蓝桥杯2023年第十四届省赛真题-更小的数
蓝桥杯2023年第十四届省赛真题-颜色平衡树
蓝桥杯2023年第十四届省赛真题-买瓜
蓝桥杯2023年第十四届省赛真题-网络稳定性