Assimilation IV (Codeforces 1525E)
Tags: Math, probabilities

Monocarp is playing a game "Assimilation IV". In this game he manages a great empire: builds cities and conquers new lands.Monocarp's empire has $$$n$$$ cities. In order to conquer new lands he plans to build one Monument in each city. The game is turn-based and, since Monocarp is still amateur, he builds exactly one Monument per turn.Monocarp has $$$m$$$ points on the map he'd like to control using the constructed Monuments. For each point he knows the distance between it and each city. Monuments work in the following way: when built in some city, a Monument controls all points at distance at most $$$1$$$ to this city. Next turn, the Monument controls all points at distance at most $$$2$$$, the turn after — at distance at most $$$3$$$, and so on. Monocarp will build $$$n$$$ Monuments in $$$n$$$ turns and his empire will conquer all points that are controlled by at least one Monument.Monocarp can't figure out any strategy, so during each turn he will choose a city for a Monument randomly among all remaining cities (cities without Monuments). Monocarp wants to know how many points (among $$$m$$$ of them) he will conquer at the end of turn number $$$n$$$. Help him to calculate the expected number of conquered points!

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 20$$$; $$$1 \le m \le 5 \cdot 10^4$$$) — the number of cities and the number of points.Next $$$n$$$ lines contains $$$m$$$ integers each: the $$$j$$$-th integer of the $$$i$$$-th line $$$d_{i, j}$$$ ($$$1 \le d_{i, j} \le n + 1$$$) is the distance between the $$$i$$$-th city and the $$$j$$$-th point.

Output: It can be shown that the expected number of points Monocarp conquers at the end of the $$$n$$$-th turn can be represented as an irreducible fraction $$$\frac{x}{y}$$$. Print this fraction modulo $$$998\,244\,353$$$, i. e. value $$$x \cdot y^{-1} \bmod 998244353$$$ where $$$y^{-1}$$$ is such number that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.

Note: Let's look at all possible orders of cities Monuments will be build in:   $$$[1, 2, 3]$$$:   the first city controls all points at distance at most $$$3$$$, in other words, points $$$1$$$ and $$$4$$$;  the second city controls all points at distance at most $$$2$$$, or points $$$1$$$, $$$3$$$ and $$$5$$$;  the third city controls all points at distance at most $$$1$$$, or point $$$1$$$.  In total, $$$4$$$ points are controlled.  $$$[1, 3, 2]$$$: the first city controls points $$$1$$$ and $$$4$$$; the second city — points $$$1$$$ and $$$3$$$; the third city — point $$$1$$$. In total, $$$3$$$ points.  $$$[2, 1, 3]$$$: the first city controls point $$$1$$$; the second city — points $$$1$$$, $$$3$$$ and $$$5$$$; the third city — point $$$1$$$. In total, $$$3$$$ points.  $$$[2, 3, 1]$$$: the first city controls point $$$1$$$; the second city — points $$$1$$$, $$$3$$$ and $$$5$$$; the third city — point $$$1$$$. In total, $$$3$$$ points.  $$$[3, 1, 2]$$$: the first city controls point $$$1$$$; the second city — points $$$1$$$ and $$$3$$$; the third city — points $$$1$$$ and $$$5$$$. In total, $$$3$$$ points.  $$$[3, 2, 1]$$$: the first city controls point $$$1$$$; the second city — points $$$1$$$, $$$3$$$ and $$$5$$$; the third city — points $$$1$$$ and $$$5$$$. In total, $$$3$$$ points.  The expected number of controlled points is $$$\frac{4 + 3 + 3 + 3 + 3 + 3}{6}$$$ $$$=$$$ $$$\frac{19}{6}$$$ or $$$19 \cdot 6^{-1}$$$ $$$\equiv$$$ $$$19 \cdot 166374059$$$ $$$\equiv$$$ $$$166374062$$$ $$$\pmod{998244353}$$$

Sample Inputs:
3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3

Sample Outputs:
166374062

Solution (Python):
import sys
input = sys.stdin.readline
get_int = lambda : int(input().rstrip())
get_arr = lambda : [int(w) for w in input().split()]
get_str = lambda : input().rstrip()
(n, m) = get_arr()
d = [get_arr() for _ in range(n)]
mod = 998244353
inv = 1
for t in range(1, n + 1):
    inv *= pow(t, -1, mod)
    inv %= mod
ans = 0
for j in range(m):
    arr = sorted((d[i][j] - 1 for i in range(n)))
    p = 1
    for k in range(n):
        val = arr[k] - k
        if val <= 0:
            p = 0
            break
        p *= val
    ans += (1 - p * inv) % mod
    ans %= mod
print(ans)

Solution (Python):
import sys
import math
input = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x) + '\n')
mod = 998244353
(n, m) = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
inv = 1
for i in range(1, n + 1):
    inv = inv * i % mod
inv = pow(inv, mod - 2, mod)
ret = 0
for i in range(m):
    cnt = [0] * (n + 2)
    for j in range(n):
        cnt[min(g[j][i], n + 1)] += 1
    s = 0
    cur = 1
    for j in range(n + 1, 1, -1):
        s += cnt[j]
        cur = cur * s % mod
        s -= 1
    ret = (ret + 1 - cur * inv) % mod
write(ret)

Solution (Python):
from math import factorial
from fractions import Fraction
(n, m) = map(int, input().split())
dji = [[] for _ in range(m)]
for i in range(n):
    for (j, x) in enumerate(map(int, input().split())):
        dji[j].append(x)
out = 0
for dj in dji:
    dj.sort()
    p = 1
    for (i, d) in enumerate(dj):
        if i + 1 >= d:
            p = 0
            break
        p *= d - i - 1
    out += p
f = m - Fraction(out, factorial(n))
print(f.numerator * pow(f.denominator, -1, 998244353) % 998244353)