Editorial for Lantern Sparks

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 $X_e$ ~X_e~ be the indicator that wire $e = (u, v)$ ~e = (u, v)~ sparks. Then $X = \sum_e X_e$ ~X = \sum_e X_e~, so

$E[X] = \sum_e E[X_e] = \sum_e \Pr(\text{wire } e \text{ sparks})$ .

The wires are not independent: two wires that share a lantern succeed or fail together more often than independent events would. Linearity does not need independence, so it is enough to compute each probability separately.

Lantern $i$ ~i~ chooses uniformly from $[l_i, r_i]$ ~[l_i, r_i]~. The number of multiples of $p$ ~p~ in that interval is $\lfloor r_i / p \rfloor - \lfloor (l_i - 1) / p \rfloor$ . Hence the probability that lantern $i$ ~i~ is not divisible by $p$ ~p~ is

$\Pr(\text{fail}_i) = 1 - \frac{\#\{x \in [l_i, r_i] : p \mid x\}}{r_i - l_i + 1}$ .

Brightnesses are chosen independently, so a wire fails only if both endpoints fail:

$\Pr(\text{wire } (u, v) \text{ sparks}) = 1 - \Pr(\text{fail}_u)\Pr(\text{fail}_v)$ .

Sum these contributions over all $m$ ~m~ wires in $O(n + m)$ ~O(n + m)~.

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

long long multiples(long long l, long long r, long long p) {
    return r / p - (l - 1) / p;
}

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

    int n, m;
    long long p;
    cin >> n >> m >> p;

    vector<long long> fail_num(n), fail_den(n);
    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        long long len = r - l + 1;
        long long good = multiples(l, r, p);
        fail_num[i] = len - good;
        fail_den[i] = len;
    }

    long long ans = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        long long den = fail_den[u] % MOD * (fail_den[v] % MOD) % MOD;
        long long none = fail_num[u] % MOD * (fail_num[v] % MOD) % MOD;
        long long ok = (den - none) % MOD;
        if (ok < 0) {
            ok += MOD;
        }
        ans += ok * modpow(den, MOD - 2) % MOD;
        if (ans >= MOD) {
            ans -= MOD;
        }
    }
    cout << ans << "\n";
}

Comments

There are no comments at the moment.