Fish

Observation 1

The only thing that matters is who is alive right now. The exact order of previous meetings does not matter at all. Once the alive set is fixed, the future depends only on that set and the matrix $a$.

So yes, this is a bitmask DP. The tags weren't trolling you.

State

Let $S$ be a subset of fish, represented by a bitmask. Define

$$dp[S] = \Pr(\text{after exactly } n-|S| \text{ eliminations, the alive fish are exactly } S).$$

This is well-defined because each day exactly one fish dies, so a subset of size $k$ can only appear after $n-k$ deaths. No cycles, no revisits, no weird nonsense.

Initially, all fish are alive:

$$dp[(1<<n)-1] = 1.$$

The final answer for fish $i$ is simply the probability that only fish $i$ remains:

$$dp[\{i\}] = dp[1<<i].$$

Transition

Suppose the current alive set is $S$ and $|S|=k$. The next meeting is chosen uniformly among all unordered pairs of alive fish, so there are

$$\binom{k}{2}$$

equally likely meetings.

Fix some fish $j \in S$. When does $j$ die next? It dies if it meets some other alive fish $i \in S \setminus \{j\}$ and then $i$ eats $j$.

For a fixed killer $i$, the pair $\{i,j\}$ is chosen with probability $\frac{1}{\binom{k}{2}}$, and then $i$ kills $j$ with probability $a_{ij}$. Summing over all possible killers gives

$$\Pr(S \to S\setminus\{j\}) = \frac{\sum_{i \in S,\ i\ne j} a_{ij}}{\binom{k}{2}}.$$

Therefore the DP transition is

$$dp[S\setminus\{j\}] \mathrel{+}= dp[S] \cdot \frac{\sum_{i \in S,\ i\ne j} a_{ij}}{\binom{|S|}{2}}.$$

That is the whole trick. Seriously. Just do not botch the denominator: the meeting is over unordered pairs, so it is $\binom{k}{2}$, not $k(k-1)$.

Order of computation

Every transition removes exactly one fish, so it always goes from a larger mask to a smaller mask. Therefore we can process masks in decreasing order, starting from the full mask.

Why this works

This process is a Markov chain on subsets of alive fish.

• The state is completely described by the alive set $S$.
• From a state $S$, the next state must be $S\setminus\{j\}$ for some $j\in S$.
• The probability of each such transition is exactly the formula above.
• Since each step decreases the number of alive fish by $1$, the subset graph is a DAG, so dynamic programming accumulates exact reachability probabilities.

By induction over decreasing subset size, $dp[S]$ is precisely the probability that the set of alive fish is exactly $S$ after $n-|S|$ eliminations. In particular, singleton masks give the probabilities of being the last surviving fish.

Complexity

There are $2^n$ masks. For each mask, we try each possible victim $j$ and sum over each possible killer $i$, so the time complexity is

$$O(n^2 2^n).$$

Memory usage is

$$O(2^n).$$

With $n \le 18$, this is easily fine.

You can precompute some sums to shave constants, but honestly, that is just competitive-programming vanity at this point. The plain DP gets Accepted.