The 3rd Universal Cup. Stage 16: Nanjing

給你 $a_{1}, a_{2}, \dots, a_{nm}$ ，你要將其由左上至右下填入 $n \times m$ 的表格 $G$ 中。定義一個表格的 bingo 數 是

$min (1 \leq r \leq n min (1 \leq c \leq m max G_{r, c}), 1 \leq c \leq m min (1 \leq r \leq n max G_{r, c}))$

請計算所有 $(nm)!$ 種 $a$ 的排列的 bingo 數之和，模 $998244353$ 。

$n \cdot m \leq 200000$

min of max 很不好算，能不能把他換成只有 max 呢？

答案是可以的！用 min-max 排容：

$x \in S min x = \emptyset ⊊ T \subseteq S \sum (- 1)^{∣ T ∣ + 1} y \in T max y$

以上算式的感性證明就是當 max 是第 $k$ 小的時候你有 $2^{k - 1}$ 種其他東西的取法，而這些除了在 $k = 1$ 的時候都會正負消掉。

固定 $a_{p}$ 為 $max T$ ，並枚舉 $T$ 中包含了幾個 row max、幾個 column max，可以得到以下算式：

$p = 1 \sum nm a_{p} r = 1 \sum n c = 1 \sum m (- 1)^{r + c + 1} (r n) (c m) (k - 1 p - 1) k! (nm - k)! (where k = r m + c n - rc)$

其中 $k$ 代表的是被 $T$ 裡的 row 跟 column 覆蓋的格子數量，max of max 讓我們只需要計算這 $k$ 個格子的 max 恰好是 $a_{p}$ 的排列數量就好。

直接做是 $O (n^{2} m^{2})$ ，得想辦法加速。令

$f_{k} = p = 1 \sum nm a_{p} \cdot (k - 1 p - 1) \cdot k! \cdot (nm - k)!$

那麼答案就是

$r = 1 \sum n c = 1 \sum m (- 1)^{r + c + 1} (r n) (c m) \cdot f_{k} (where k = r m + c n - rc)$

把二項式拆開， $f_{k}$ 可以整理成如下形式，注意下標從 $k$ 開始：

$f_{k} = p = k \sum nm \frac{a _{p} \cdot ( p - 1 )! \cdot k \cdot ( nm - k )!}{( p - k )!}$

把只跟 $k$ 有關的提出來變成 $z_{k}$ ，剩下的式子能整理成 $f_{k} = z_{k} \cdot \sum_{p = k}^{nm} x_{p} \cdot y_{p - k}$ 的形式，感覺跟卷積很像了？

$x_{p} = a_{p} \cdot (p - 1)!$
$y_{p - k} = (p - k)!^{- 1}$
$z_{k} = k \cdot (nm - k)!$

$⟨ x ⟩, ⟨ y ⟩, ⟨ z ⟩$ 都是能預處理的，於是我們將 $⟨ x ⟩$ 先 reverse 讓 $\sum$ 裡面變成 $x_{nm - p} \cdot y_{p - k}$ 的形式，讓 $f_{k} = z_{k} \cdot (x * y)_{nm - k}$ ，這題就能開心的用 NTT 解決掉了！

時間複雜度： $O (nm lo g (nm))$ 。

SorahISA's Contest Logs

The 3rd Universal Cup. Stage 16: Nanjing

Problem A. Hey, Have You Seen My Kangaroo?

Problem B. Birthday Gift

Tags: `observation`

Problem C. Topology

Problem D. Toe-Tac-Tics

Problem E. Left Shifting 3

Problem F. Subway

Problem G. Binary Tree

Tags: `interactive`

Problem H. Border Jump 2

Problem I. Bingo

Tags: `inclusive-exclusive`, `ntt`

Tags: N/A

Problem K. Strips

Tags: `greedy`

Problem L. $P \oplus Q = R$

Problem M. Ordainer of Inexorable Judgment