Divisor Card Game

Key simplification

When card $i$ with value $a_i$ is revealed, a student matters only if they currently own some multiple of $a_i$. That student chooses their smallest such multiple. Then the game picks the smallest chosen divisible value.

So globally, the winner is simply:

the owner of the smallest currently owned card $j$ such that $a_i \mid a_j$.

Good. The classroom-card-game cosplay is gone; now it is a random process on divisibility.

Good and bad undealt cards

Call an initially undealt card $i$ good if some initially owned card is a multiple of it:

$$\exists j \text{ with } b_j \ne 0 \text{ and } a_i \mid a_j.$$

If $i$ is good, then whenever it is revealed, that initially owned multiple is already sitting there, so $i$ is definitely won.

If $i$ is not good, it can never be won. Suppose it were won by some zero card $j$. Then $j$ was already won earlier, so following the ownership chain upward eventually reaches an initially owned card $r$. Since every edge is divisibility,

$$a_i \mid a_j \mid \cdots \mid a_r,$$

which means $i$ had an initially owned multiple after all. Contradiction. Boom, fake complexity deleted.

Bad undealt cards are always discarded and can be ignored.

Random times

Instead of thinking about rounds, assign every initially undealt card an independent random reveal time in $[0,1]$. Only relative order matters.

For a good undealt card $i$, scan indices $j>i$ in increasing order and keep only multiples of $i$.

During this scan:

• bad undealt cards are ignored, since they are never owned;
• good undealt cards may be owned before time $t$;
• initially owned cards are owned from the start;
• once we hit the first initially owned multiple, we can stop, because anything after it is larger and can never be the smallest owned multiple if this root is available.

Let:

• $C_i$ be the good undealt multiples before that first initially owned multiple;
• $r_i$ be that first initially owned multiple;
• $z(i,j)$ be the number of cards from $C_i$ appearing before candidate $j$ in the scan;
• $z_i=|C_i|$.

If card $i$ is revealed at time $t$, a candidate $j\in C_i$ wins exactly when:

1. all earlier candidates in $C_i$ have reveal time $>t$, contributing $(1-t)^{z(i,j)}$;
2. card $j$ has already been revealed and won by time $t$.

Let $P_j(t)$ be the owner-distribution vector of card $j$ being already owned by time $t$. Then the winner distribution at reveal time $t$ is

$$Q_i(t)=\sum_{j\in C_i}(1-t)^{z(i,j)}P_j(t)+(1-t)^{z_i}e_{owner(r_i)},$$

where $e_s$ is the unit vector for student $s$.

The final owner distribution of card $i$ is therefore

$$F_i=\int_0^1 Q_i(t)\,dt.$$

Also,

$$P_i(t)=\int_0^t Q_i(u)\,du.$$

Moments

Directly storing all $P_i(t)$ vectors for all students would be bulky as hell. Instead define moments:

$$M_i[d]=\int_0^1(1-t)^dP_i(t)\,dt.$$

Now use Fubini:

$$\begin{aligned} M_i[d] &=\int_0^1(1-t)^d\int_0^t Q_i(u)\,du\,dt \\ &=\int_0^1 Q_i(u)\int_u^1(1-t)^d\,dt\,du \\ &=\frac{1}{d+1}\int_0^1(1-u)^{d+1}Q_i(u)\,du. \end{aligned}$$

Substitute the formula for $Q_i$:

$$M_i[d] =\frac{1}{d+1} \left( \sum_{j\in C_i}M_j[d+1+z(i,j)] +\frac{e_{owner(r_i)}}{d+2+z_i} \right).$$

Similarly, the final distribution of card $i$ is

$$F_i= \sum_{j\in C_i}M_j[z(i,j)] +\frac{e_{owner(r_i)}}{z_i+1}.$$

All divisions are modulo $998244353$ using modular inverses.

Reverse DP trick

The recurrence is linear. Instead of computing vector-valued $M_i[d]$, store scalar coefficients saying how much the final answer needs each state.

Let $need[i][d]$ be the coefficient of vector state $M_i[d]$ in the final answer.

Initialize answers with initially owned cards. For each good undealt card $i$, its final distribution $F_i$ says:

• for every $j\in C_i$, add $1$ to $need[j][z(i,j)]$;
• add $1/(z_i+1)$ directly to the owner of $r_i$.

Then process states in increasing index. This is topological because every $M_i[d]$ depends only on states $M_j[*]$ with $j>i$.

For a pending coefficient $\alpha=need[i][d]$:

$$M_i[d] =\frac{1}{d+1} \left( \sum_{j\in C_i}M_j[d+1+z(i,j)] +\frac{e_{owner(r_i)}}{d+2+z_i} \right).$$

So:

• push $\alpha/(d+1)$ to each $need[j][d+1+z(i,j)]$;
• add $\alpha/((d+1)(d+2+z_i))$ directly to the owner of $r_i$.

The exponent $d$ never needs to exceed $n$: every increase accounts for new lower-index good zero cards forced to appear after some reveal time, and those cards are all distinct. In code, allocating $n+5$ columns is plenty.

Complexity

We precompute divisibility in $O(n^2)$. The reverse DP has $O(n^2)$ states and scans candidate lists, giving $O(n^3)$ worst-case time and $O(n^2)$ memory. With $n\le 600$, that is exactly the kind of ugly-but-fine DP this problem wants.