Problem 73: Sum Over Subsets DP
Problem Statement: Given an array of n integers, compute for every subset the sum of its elements, and then compute the total of all these subset sums modulo 10^9+7.
Input
The first line contains an integer n. The second line contains n space-separated integers.
Output
Print the total sum of all subset sums modulo 10^9+7.
Examples
Input:
3
1 2 3
Output:
24
Solution Explanation
Each element appears in exactly 2^(n-1) subsets. Therefore, the answer is (sum of elements) * 2^(n-1) modulo 10^9+7.
Solution in C++
#include
#include
using namespace std;
const long long MOD = 1000000007;
long long modExp(long long base, int exp){
long long res = 1;
while(exp){
if(exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
int main(){
int n;
cin >> n;
long long sum = 0;
for(int i = 0; i < n; i++){
int x;
cin >> x;
sum = (sum + x) % MOD;
}
long long ans = (sum * modExp(2, n - 1)) % MOD;
cout << ans << "\n";
return 0;
}