Minesweeper String

Research checked: the canonical statement is the Codeforces problem page (https://codeforces.com/contest/2206/problem/F). The official tutorial PDF (https://codeforces.com/contest/2206/attachments/download/36244/analysis.pdf) gives the intended base-minus-reductions idea with convolution plus divisor/range handling. The public status page (https://codeforces.com/contest/2206/status/F) confirms accepted C++ submissions, though individual source pages were blocked by Codeforces browser checking here.

Let $a_i$ be the digit at position $i$. A zero cell contributes nothing by itself; it only receives mine counts from adjacent mined cells. So for a fixed width $w$,

$f(w)=\sum_{i:a_i>0} a_i\cdot(\text{number of adjacent zero cells of }i).$

Start with $4a_i$ for every mined cell, as if all four neighboring directions existed and were zero. Then subtract $a_i$ for each direction that fails because the neighbor is missing or because the neighbor also has mines. Thus

$f(w)=4\sum_i a_i-R(w).$

Now compute $R(w)$ for all $w=1,\dots,n$.

Vertical mined pairs

Cells $i$ and $i+w$ are vertical neighbors. If both contain mines, the base counted both directions incorrectly, so the reduction is $a_i+a_{i+w}$. Equivalently,

$V_w=\sum_{i=0}^{n-1-w} a_i[a_{i+w}>0]+a_{i+w}[a_i>0].$

Use one convolution. Define

$P_t=a_t,\qquad Q_t=[a_{n-1-t}>0].$

Then the coefficient of $x^{n-1-w}$ in $P(x)Q(x)$ equals

$\sum_i a_i[a_{i+w}>0],$

and the coefficient of $x^{n-1+w}$ equals

$\sum_i a_i[a_{i-w}>0].$

So for $w<n$, add both coefficients. Since coefficients are at most $9n$, one NTT modulo $998244353$ is exact. No floating-point clownery required.

Missing vertical neighbors

A mined cell at position $p$ has no upper neighbor iff $p-w<0$, i.e. $w\in[p+1,n]$.

It has no lower neighbor iff $p+w\ge n$, i.e. $w\in[n-p,n]$. This condition also handles the truncated bottom row correctly. Do not assume only cells in the last visual row lose downward adjacency; cells above missing columns can lose it too.

For every nonzero $a_p$, add $a_p$ to both ranges with a difference array.

Horizontal gaps

Look at the gap between positions $m-1$ and $m$, where $1\le m<n$. This gap is a row break exactly when $w\mid m$.

If $w\nmid m$, the cells are horizontally adjacent. The only reduction from this gap happens when both endpoints are mined, costing $a_{m-1}+a_m$.

If $w\mid m$, they are not adjacent. The right side of $m-1$ and the left side of $m$ are missing, so the reduction is $a_{m-1}+a_m$ from whichever endpoints are mined.

Therefore:

• if both endpoints are mined, this gap costs $a_{m-1}+a_m$ for every width;
• otherwise, this gap costs $a_{m-1}+a_m$ only for divisor widths $w\mid m$.

Add the both-mined gap total to every width. For the remaining gaps, add their cost to every divisor width by looping over multiples: for each $w$, visit $m=w,2w,3w,\dots<n$.

Finally, the outer left side of cell $0$ and outer right side of cell $n-1$ are missing for every width, so add $a_0+a_{n-1}$ to every width.

After all reductions are known, compute

$f(w)=4\sum_i a_i-R(w),$

then use nth_element with descending order to get the $k$-th largest value.

Edge cases are naturally covered: all zeros give all $0$, $n=1$ gives $0$ because the single cell has no adjacent cells, $w=1$ makes every internal gap a row break, and $w=n$ makes one row with no vertical neighbors.

Complexity is $O(n\log n)$ time from the NTT and divisor/multiple loops, and $O(n)$ memory.