Turing Hut's Peer-to-Peer Learning Sessions

Author : shailesh_2004

Required Knowledge : Combinatorics, Modular Inverse

Time Complexity : $O(N\cdot log_2{(10^9+7)})$

Editorialist : shailesh_2004

Approach:

Use a hashmap to count the frequency of each unique value in the array.

Even if a number appears multiple times, we’re only allowed to include it at most once in a subsequence. But since it occurs multiple times, we have multiple choices for its position in the subsequence.

For each unique number $v$ with count $c$ : We can either skip it or choose it(in one of its c positions).

That gives us $(c+1)$ choices per number.

Now we compute the total sum of these valid subsequences(excluding the empty one).

But instead of generating them, we compute the contribution of each number to all the subsequences it's in.

For a number $v$ with frequency $c$:

There are $\frac{Total}{c+1}$ subsequences that include $v$.

And it appears $c$ times in the original array → so contributes $c \cdot v$ total.

So contribution of $v$ is:

$contribution = v \cdot c \cdot \frac{Total}{c + 1}$

To compute this use modular inverse and find the total sum.

Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element
 
// ------------------------------------------------------------------------------------
 
ll binexp(ll a, ll b, ll mod2 = mod) {
    ll res = 1;
    a %= mod2;
    while (b) {
        if (b % 2)res = (res * a) % mod2;
        a = (a * a) % mod2;
        b >>= 1;
    }
    return res;
}
 
ll modular_inverse(ll a, ll mod2 = mod) {
    // By Fermat's little theorem
    return binexp(a, mod2 - 2, mod2);
}
 
// ------------------------------------------------------------------------------------
 
vll modinv(1e5+1);
 
void precompute_modinv() {
    for (ll i = 0;i < modinv.size();i++) {
        modinv[i] = modular_inverse(i);
    }
}
 
void solve() {
    ll n;
    cin >> n;
    ll a[n], i;
    map<ll, ll>mp;
    for (i = 0;i < n;i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    ll mul = 1;
    for (auto it = mp.begin();it != mp.end();it++)mul = (mul * (it->second + 1)) % mod;
    ll ans = 0;
    for (auto it = mp.begin();it != mp.end();it++) {
        ll val = it->first;
        ll freq = it->second;
        ll dup = (mul * modinv[freq + 1]) % mod;
        ans = (ans + ((dup * freq) % mod * val) % mod) % mod;
    }
    cout << ans << endl;
}
 
// ------------------------------------------------------------------------------------
 
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    precompute_modinv();
    ll t;cin >> t;while (t--)
    solve();
    return 0;
}