Editorial for Expected Fixed Points

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let $I_i$ ~I_i~ be the indicator that person $i$ ~i~ receives gift $i$ ~i~. The total value is

$X = \sum_{i=1}^n w_i I_i$ ~X = \sum_{i=1}^n w_i I_i~.

By linearity of expectation,

$E[X] = \sum_{i=1}^n w_i E[I_i] = \sum_{i=1}^n w_i \Pr(I_i = 1)$ .

In a uniformly random permutation, person $i$ ~i~ is equally likely to receive any of the $n$ ~n~ gifts, so $\Pr(I_i = 1) = 1/n$ ~\Pr(I_i = 1) = 1/n~. Therefore

$E[X] = \frac{1}{n} \sum_{i=1}^n w_i$ ~E[X] = \frac{1}{n} \sum_{i=1}^n w_i~.

The events $I_i$ ~I_i~ are dependent (exactly one person can receive gift $1$ ~1~, for example), but linearity does not care. Output the fraction modulo $10^9 + 7$ ~10^9 + 7~.

This is $O(n)$ ~O(n)~.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

long long modpow(long long a, long long e) {
    long long r = 1;
    a %= MOD;
    while (e) {
        if (e & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long w;
        cin >> w;
        sum += w;
        if (sum >= MOD) {
            sum %= MOD;
        }
    }
    sum %= MOD;
    cout << sum * modpow(n, MOD - 2) % MOD << "\n";
}

Comments

There are no comments at the moment.