Editorial for Expected Fixed Points

Use this editorial only when stuck, and do not 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$ be the indicator that person $i$ receives gift $i$ . The total value is

$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$ is equally likely to receive any of the $n$ gifts, so $\Pr(I_i = 1) = 1/n$ . Therefore

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

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

This is $O(n)$ .

Solution (C++)

Code 1

#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";
}

Comments0

No comments yet

Be the first to comment.

Editorial for Expected Fixed Points

Approach

Solution (C++)

Comments0

New comment