Problem : 204 - Balanced Cow Subsets

Problem Statistics

Solved Member: 6　　Submission: 34　　User Tried: 8

Statement:

自從上次(上一題)某条破完那個工口遊戲之後，他現在擁有了 N (2 <= N <= 20)隻蘿莉。

每一隻蘿莉身上都穿有一件用魔法構成的衣服，會在蘿莉身邊產生一種名叫「移動教會」的終極防禦結界來保護蘿莉，並且每一隻蘿莉的「移動教會」的魔力值 Mi (1 <= Mi <= 100,000,000) 不完全一樣。

不過厲害的是某条和上條(當麻)是遠房親戚，所以他的兩隻手都有能夠輸出反魔力物質，以消退「移動教會」的魔力，當輸出的量和「移動教會」的魔力值一樣的時候，「移動教會」就會被破壞，如下圖。順帶一提這能力叫做「幻想殺手」。

不過某条的「幻想殺手」有一個發動條件，就是兩隻手輸出的反魔力物質總和要一樣，否則兩隻手都會斷掉，然後就QQ了。

另外每次輸出的反魔力物質和魔力交互作用之後就會消失，而宇宙的熵的總和也會減少，所以一單位的反魔力物質只能和一單位的魔力反應。

現在某条想要知道他有多少種方式，可以從所有蘿莉中挑選一些來進行反應，並且不會讓他的手斷掉。左手邊的蘿莉和右手邊的蘿莉位置對調視為同一種方式。

相同魔力值的蘿莉，在計算方法數時，視為同一種。

Input:Output:

第 1 行有一個數字 N。

第 2~N+1 行分別代表每一隻蘿莉的魔力值 Mi 。

輸出一行，代表總共挑選蘿莉的方法數。

Sample Input:Sample Output:

4
1
2
3
4

HINT:

有三種挑選蘿莉的方式：{1,2,3}可分為{1,2},{3}；{1,3,4}可分為{1,3},{4}；{1,2,3,4}可分為{1,4},{2,3}。

2012/11/4 08:54 補上題敘

Source:

USACO Open 2012 Gold.

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	131072kb
1	500ms	131072kb	5
2	500ms	131072kb	5
3	500ms	131072kb	5
4	500ms	131072kb	5
5	500ms	131072kb	5
6	500ms	131072kb	5
7	500ms	131072kb	5
8	500ms	131072kb	5
9	500ms	131072kb	5
10	500ms	131072kb	5
11	700ms	131072kb	5
12	700ms	131072kb	5
13	700ms	131072kb	5
14	700ms	131072kb	5
15	700ms	131072kb	5
16	700ms	131072kb	5
17	700ms	131072kb	5
18	700ms	131072kb	5
19	700ms	131072kb	5
20	700ms	131072kb	5