SUMMATION - SUMMATION
You are given an array of integer. You have to find the sum of all possible subsequences sum of the array. For example: The given array of length n = 3 is {1, 2, 3}. All the subsequences of this array with the corresponding array summations are:
Subsequence | Summation |
{} | 0 |
{1} | 1 |
{2} | 2 |
{3} | 3 |
{1,2} | 3 |
{1,3} | 4 |
{2,3} | 5 |
{1,2,3} | 6 |
Total | 24 |
The answer is 24.
Input
The first line of input will contain the test case T (1 <= T <= 10). There will be two lines for each test case. First line will contain the value of n (1 <= n <= 1000) and the next line will contain the array elements space-separated integers. Each integer will be between 1 and 1000000000.
Output
For each case of input, output the answer of the problem in the format "Case X: Y" where X denotes the number of the test case and Y denotes the answer. Answer could be very large so output the answer modulo 100000007.
Example
Input: 2 3 1 2 3 3 4 1 2 Output: Case 1: 24 Case 2: 28
hide comments
DK...:
2019-05-26 08:59:38
Be careful about the spaces in the output format. |
|
akjol2049:
2018-11-25 10:26:25
Be careful with the mod. 10^8+7 |
|
sanyam19:
2018-06-28 17:39:37
Repeating nos., Pattern ,derive a Formula ,thats it... :p |
|
fuggu_13:
2018-03-25 22:33:33
AC in one go!! My 50th :D |
|
prakash1108:
2018-03-20 15:38:30
Easy af AC in 1 Go :xD |
|
venkat016:
2018-01-16 15:44:09
any tricky test cases. test with all test cases in spoj toolkit but still get WA :( |
|
nadstratosfer:
2017-12-18 16:52:06
jaykay12, mahilewets' comment below is a big hint (a Python program doing nothing takes 0.02s on SPOJ). |
|
jaykay12:
2017-12-17 20:10:05
Recursive approach giving TLE & iterative using bitwise giving WA :( Any suggestions? |
|
mahilewets:
2017-08-20 10:43:22
Python 3.5 AC 0.05 sec 28 MB |
|
ayushgupta1997:
2017-08-13 11:18:41
@aditya_97 element can occur more than once but you should treat them different ,don't know why? |
Added by: | Bhadra |
Date: | 2017-07-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |