Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 590 Accepted Submission(s): 136
Teacher Mai is addicted to game 2048. But finally he finds it’s too hard to get 2048. So he wants to change the rule:
You are given some numbers. Every time you can choose two numbers of the same value from them and merge these two numbers into their sum. And these two numbers disappear meanwhile.
If we can get 2048 from a set of numbers with this operation, Teacher Mai think this multiset is good.
You have n numbers, A1,…,An. Teacher Mai ask you how many subsequences of A are good.
There are multiple test cases, terminated by a line “0”.
For each test case, the first line contains an integer n (1<=n<=10^5), the next line contains n integers ai (0<=ai<=2048).
Case #1: 1 Case #2: 11 Case #3: 8
In the first case, we should choose all the numbers. In the second case, all the subsequences which contain more than one number are good.