两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

Dotcpp  >  編程題庫  >  藍(lán)橋杯2023年第十四屆省賽真題-數(shù)組分割
題目 3171:

藍(lán)橋杯2023年第十四屆省賽真題-數(shù)組分割

時(shí)間限制: 2s 內(nèi)存限制: 576MB 提交: 4183 解決: 872

題目描述

小藍(lán)有一個(gè)長(zhǎng)度為 N 的數(shù)組 A = [A0, A1,..., AN?1]。現(xiàn)在小藍(lán)想要從 A 對(duì)應(yīng)的數(shù)組下標(biāo)所構(gòu)成的集合 I = {0, 1, 2, . . . , N ? 1} 中找出一個(gè)子集 R1，那么 R1在 I 中的補(bǔ)集為 R2。記 S1=∑r∈R1Ar，S2 =∑r∈R2Ar，我們要求 S1 和 S2 均為偶數(shù)，請(qǐng)問在這種情況下共有多少種不同的 R1。當(dāng) R1 或 R2 為空集時(shí)我們將 S1 或 S2 視為 0。

輸入格式

第一行一個(gè)整數(shù) T，表示有 T 組數(shù)據(jù)。
接下來輸入 T 組數(shù)據(jù)，每組數(shù)據(jù)包含兩行：第一行一個(gè)整數(shù) N，表示數(shù)組 A 的長(zhǎng)度；第二行輸入 N 個(gè)整數(shù)從左至右依次為 A0, A1, . . . , AN?1，相鄰元素之間用空格分隔。

輸出格式

對(duì)于每組數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)表示答案，答案可能會(huì)很大，你需要將答案對(duì)1000000007 進(jìn)行取模后輸出。

樣例輸入

2
2
6 6
2
1 6

樣例輸出

4
0

提示

對(duì)于第一組數(shù)據(jù)，答案為 4。（注意：大括號(hào)內(nèi)的數(shù)字表示元素在數(shù)組中的下標(biāo)。）
R1 = {0}, R2 = {1}；此時(shí) S1 = A0 = 6 為偶數(shù), S2 = A1 = 6 為偶數(shù)。
R1 = {1}, R2 = {0}；此時(shí) S1 = A1 = 6 為偶數(shù), S2 = A0 = 6 為偶數(shù)。
R1 = {0, 1}, R2 = {}；此時(shí) S1 = A0 + A1 = 12 為偶數(shù), S2 = 0 為偶數(shù)。
R1 = {}, R2 = {0, 1}；此時(shí) S1 = 0 為偶數(shù), S2 = A0 + A1 = 12 為偶數(shù)。

對(duì)于第二組數(shù)據(jù)，無論怎么選擇，都不滿足條件，所以答案為 0。


對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。
對(duì)于 40% 的評(píng)測(cè)用例，1 ≤ N ≤ 102。
對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ T ≤ 10, 1 ≤ N ≤ 103 , 0 ≤ Ai ≤ 109。


標(biāo)簽
 
分享