Editorial for Danger at the Marks

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

The input provides a matrix A. We can see that A^k_{i,j} gives us the probability of ending at position j after k steps, when starting from position i.

For a given start s:

E[\text{Collisions}] = \sum_t \Pr[\text{Collision at time } t]

(by linearity of expectation)

= \sum_t \sum_{i=1}^{n} A^t_{s,i} A^t_{1,i}.

A collision at time t occurs precisely when Eric and Lucas occupy the same mark. They move independently, so the probability they both land at mark i is A^t_{s,i} A^t_{1,i}, and summing over i gives the probability of a collision. The same sum is the (s, 1) entry of A^t (A^t)^\top, since

(A^t (A^t)^\top)_{s,1} = \sum_{i=1}^{n} A^t_{s,i} ((A^t)^\top)_{i,1} = \sum_{i=1}^{n} A^t_{s,i} A^t_{1,i}.

The expectation is then \sum_t (A^t (A^t)^\top)_{s,1}. Matrix addition is entrywise, so this is the (s, 1) entry of \sum_t A^t (A^t)^\top. (It turns out, entry (x, y) gives us the EV for Lucas starting at x, and Eric starting at y.)

Naively calculating this takes O(n^3 k), which is not fast enough. We can find a recurrence to speed this up.

Define f(k) to equal the sum from 1 to k:

f(k) = \sum_{t=1}^{k} A^t (A^t)^\top.

f(0) is the zero matrix.

f(k) = A f(k - 1) A^\top + A A^\top when k is odd.

f(k) = A^{k/2} f(k/2) (A^\top)^{k/2} + f(k/2) when k is even.

Using this recurrence, and being careful to calculate all required powers of A with \log k matrix multiplications, we can evaluate f in O(n^3 \log k).

Solution (C++)

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define nl '\n'
#define fr first
#define sc second
typedef long long ll;
typedef pair<int, int> pii; typedef vector<int> vi;

const ll mod = 1e9 + 7;

ll modpow(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p&1)res=res*a%mod;
        a=a*a%mod;
        p/=2;
    }
    return res;
}

const ll inv100 = modpow(100, mod-2);
typedef vector<array<ll,100>> mat;
int n;

mat matmul(const mat &a, const mat &b) {
    mat res(n);
    rep(i,0,n) rep(j,0,n) rep(k,0,n) {
        (res[i][j] += a[i][k] * b[k][j]) %= mod;
    }
    return res;
}

mat matadd(const mat &a, const mat &b) {
    mat res(n);
    rep(i,0,n) rep(j,0,n) res[i][j] = (a[i][j] + b[i][j])%mod;
    return res;
}

// :3
mat trans(const mat &a) {
    mat res(n);
    rep(i,0,n) rep(j,0,n) {
        res[i][j] = a[j][i];
    }
    return res;
}

mat id;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll k;
    cin >> n >> k;

    id = mat(n);
    rep(i,0,n) id[i][i] = 1;

    mat graph(n);

    rep(i,0,n) rep(j,0,n) {
        cin >> graph[i][j];
        (graph[i][j] *= inv100) %= mod;
    }


    mat grapht = trans(graph);

    // graph^k, sum
    auto recurse = [&](auto && self, ll k) -> array<mat,2> {
        if (k == 0) return {id, mat(n)};
        if (k % 2 == 0) {
            auto [ha,sum] = self(self, k/2);
            auto a = matmul(ha,ha);
            auto nw = matmul(matmul(ha, sum), trans(ha));
            nw = matadd(nw, sum);

            return {a,nw};
        } else {
            auto [ha,sum] = self(self,k-1);
            auto a = matmul(ha,graph);
            auto nw = matmul(matmul(graph,sum),grapht);
            nw = matadd(nw, matmul(graph,grapht));
            return {a,nw};
        }
    };

    auto [a,res] = recurse(recurse,k);
    rep(i,1,n) cout << res[i][0] << " \n"[i == n - 1];
}

Comments

There are no comments at the moment.