observations
The number of non-empty subsequences of an array of length n is 2n - 1. If each number in the array appears once, then this is the answer.
The order of the numbers in the array does not affect the count, just the number frequencies.
Why is observation one true: each number can either appear or not appear, and the empty set is not counted, so (1 + 1)...(1 + 1) - 1 = 2n - 1. Each number contributes a term of (1 + 1): the first one is absence, while the second one is incidence.
But what if a number occurs more than once? A subsequence can either not have a number or have just one instance of it. That "choice" is easily expressed as a trivial combination: (frequency of number choose 1) = frequency of number. The expression for the general answer is (1 + frequency of first number)(1 + frequency of second number)...(1 + frequency of last number) - 1.
You could feasibly compute this expression directly mod 1e9+7, but there is a cooler incremental, indirect computation.
solution
#include<iostream>
#include<unordered_map>
using namespace std;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main() {
const long long MOD = 1000000007;
int n;
cin >> n;
unordered_map<int, int> freq;
long long count = 1;
for (int i = 0;i < n;++i) {
int x;
cin >> x;
count = count + (count * binpow(freq[x] + 1, MOD - 2, MOD) % MOD) % MOD;
++freq[x];
}
count = count - 1 % MOD;
cout << count << endl;
}