2024 ICPC Asia West Continent Final Contest

連結：https://vjudge.net/contest/708769
時間：2025 Apr 12, 04:00-09:00
團隊：SorahISA
成績：5 / 9, Penalty 751, dirt 50% ( A B C D E F G H I )

A. Basic Vocabulary

給定 $n$ ，請求出任意一組 $1 < b_{2} < b_{1} < n$ 滿足「 $n$ 的 $b_{1}$ 進位表示法」是「 $n$ 的 $b_{2}$ 進位表示法」的前綴。不存在這樣的 $b_{1}, b_{2}$ 時，請輸出 -1。

測資數量 $\leq 300000$ 、 $1 \leq n \leq 1 0^{18}$

B. Bop to the Top

給定一個長度 $n$ 的整數序列 $⟨ h ⟩$ ，你可以對他不斷執行以下兩種操作：

選定 $1 \leq i \leq n - 1$ ，把 $h_{i}$ 跟 $h_{i + 1}$ 都 $+ 1$ 。

選定 $1 \leq i \leq n - 2$ ，把 $h_{i}$ 、 $h_{i + 1}$ 、 $h_{i + 2}$ 都 $+ 1$ 。

請輸出能否在有限次操作內使 $⟨ h ⟩$ 變成等差數列。

多筆測資、 $\sum n \leq 100000$ 、 $1 \leq h_{i} \leq 100000$

等差數列就是差分都要相同（ $h_{2} - h_{1} = h_{3} - h_{2} = \dots = h_{n} - h_{n - 1}$ ）。以下定義 $d_{i} = h_{i + 1} - h_{i}$ 。

觀察到你可以對一段長度 $\geq 2$ 的前綴或後綴 $+ 1$ ，也就是能夠單獨調整除了 $d_{1}$ 跟 $d_{n - 1}$ 以外的所有 $d_{i}$ 。又因為 $d_{1}$ 只可能上升、 $d_{n - 1}$ 只可能下降，於是只要判斷 $[d_{1}, d_{n - 1}]$ 非空，即 $d_{1} \leq d_{n - 1}$ 就好。

時間複雜度： $O (n)$ （瓶頸在輸入）

C. Fiendish Five

D. Modular Inverse Square Sum

E. Parker Rectangle

給定 $n$ ，請構造一個 $r \times c$ 的非負整數矩陣 $A$ ，滿足

$1 \leq r, c \leq n$ 且 $r + c = n$ 。

$A_{i_{1}, j_{1}} \neq = A_{i_{2}, j_{2}}$ if $(i_{1}, j_{1}) \neq = (i_{2}, j_{2})$ 。

$0 \leq A_{i, j} \leq 1 0^{9}$ 。

$\sum_{i = 1}^{r} A_{i, 1}, \sum_{i = 1}^{r} A_{i, 2}, \dots, \sum_{i = 1}^{r} A_{i, c}, \sum_{j = 1}^{c} A_{1, j}, \sum_{j = 1}^{c} A_{2, j}, \dots, \sum_{j = 1}^{c} A_{r, j}$ 這 $r + c$ 個和的全距 $\leq ⌈ \frac{n}{2} ⌉$ 。

如果沒有滿足條件的矩陣，請輸出 -1。

多筆測資、 $\sum n^{2} \leq 2^{20}$

F. Seating Sweethearts

水題，跳過

G. Skill Issue

H. The Cabins in the Woods

I. Weightiest Watermelon

$n$ 個點沒有對稱邊的簡單有向圖總共有 $3^{(2 n)}$ 種。定義 $w (G)$ 如下：

$w (G) = {0, # {v : d^{-} (v) = 0}, 如果 G 不是 DAG 如果 G 是 DAG$

給定 $n, p$ ，請求出所有 $3^{(2 n)}$ 種 $G$ 的 $w (G)$ 的總和，模 $p$ 輸出。

$n \leq 2000$ 、 $1 0^{8} < p < 1 0^{9}$ 、 $p$ 為質數

考慮分開計算每個點的貢獻，最後再乘上 $n$ 。

一個入度為零的點可以向其他點任意連邊都不會破壞 DAG 的性質，於是要計算的值變成

$n \times 2^{n - 1} \times (n - 1 個點的 DAG 數量)$

令 $a_{k}$ 是 $k$ 個點的 DAG 數量，我們可以用如下方法計算得到：

$a_{k} = i = 1 \sum k (- 1)^{i + 1} (i k) 2^{i (k - i)} \cdot a_{k - i}$

其中，我們從這 $k$ 個點以 $(i k)$ 種方法選擇 $i$ 個點出來當作入度為零的點，然後這 $i$ 個點可以向剩下 $k - i$ 個點任意連邊，總共有 $2^{i (k - i)}$ 種方法。最後，剩下的 $k - i$ 個點就變成了 $a_{k - i}$ 。為了避免重複計算，要加上排容係數 $(- 1)^{i + 1}$ 。

預處理階乘逆元跟二的冪次直接計算就是 $O (n^{2})$ 的了！

看起來有 $O (n lo g n)$ 的計算方法？ref

SorahISA's Contest Logs