## 第一屆Chi怪壓常比賽 題解

首先，先感謝大家參加這次的比賽，有意見也可以私訊我! 以下是最後的記分板:


接著下面是題解 :

## pA - 區間最小值總和問題

### 題意

給你一個長度為 $N$ 的正整數數列，定義 $\text{MIN(S)}$ 代表一個集合 $S$ 裡面最小的那個值，想請你求 $\sum_{l=1}^N \sum_{r=l}^N \text{MIN}(A_l, A_{l+1}, ... , A_r)$

如果直接照題目所講的做，會是 $O(N^3)$ 或 $O(N^2)$，但這題 $N \leq 10^6$ ，可以說是幾乎不可能通過。

### $O(N)$ 的優化

如果我們窮舉 $R$ ，有沒有辦法移動一格就 $O(1)$ 算出區間 $[1,R],[2,R],...,[R,R]$ 的答案呢? 其實是可以的，我們發現從右到左，$\text{MIN}$的值其實是單調的，所以可以使用單調堆疊 (monotone stack)，紀錄兩個元素 $(x,y)$，代表大小和區間長度，如果現在插入的元素 $\geq$ 棧頂的大小，那就 $\text{push}$ 一個新的進去，否則就 $\text{pop}$ 出來 (代表答案變小)，計算「被變小」多少，之後把這些區間合併成一個新的，放一個新的進去，時間複雜度為$O(N)$。

另外這題似乎也有很多 $O(NlogN)$ 的作法，如果常數不大應該也會通過。

## pB - 尼姆樹

### 題意

給你 $N$ 個點、帶邊權的樹 $T$，有兩個人要在 $T$ 上玩遊戲，一開始 $1$ 上面放了一個棋子，兩個人輪流進行操作，每一個操作是選擇任何一個在棋子目前位置周遭邊權 $> 0$ 的邊，把棋子移到邊上另一頭的點，並選擇任何小於等於該邊邊權的正整數 $x$，把剛剛經過的邊權減少 $x$，不停輪流操作直到某一方無法進行任何操作結束，我們定義進行最後一個操作的人獲勝。請問，如果兩個人使用最佳策略，那最終是誰會獲勝?

我們可以先想想看如果邊權都是 $1$ 會如何。

### $W_i=1$

先觀察到一個性質，就是其實因為樹是一種二分圖，所以其實兩個人能做決定的點不會相干，如下圖 :

如果邊權都是 $1$，我們可以把他想像成一個有方向的邊 (因為一定只能從起點那邊走過來，然後不能走回去) ，而最下面的葉節點，踩到那點的人就輸了，例如上圖的點 $3, 5$，我們可以定義 $dp_v$ 代表踩到 $v$ 的人最後會贏/輸，接著可以透過他的子節點的 $dp'$ 做計算，轉移式是 : 因為下面的是對手的，如果至少有一個 $dp'$ 是輸的，那 $dp_v$ 就會是贏，否則 $dp_v$ 會輸。

我們定義把全部邊權改成 $1$ 的樹叫做 $T'$。

### $W_i \neq 1$

接著我們回來討論我們想要的， $T$ 的答案，我們一樣定義 $dp$ ，對一個決策點 $v$ ，假設我們知道 $v$ 以下的子樹的結果，如果 $dp_v$ 是贏的，那他明顯會走向會讓他贏的點，也就是 $dp'$ 是輸的點，並且直接把邊走完。

如果 $dp_v$ 是輸的，因為隨便選一個點下走，不論有沒有把邊權用光都沒差，在子節點上，另一個人(會贏的)肯定會繼續往下走並且走完，所以其實 $T$ 的答案和 $T'$ 一樣。

我們可以透過 $\text{dfs}$ 以 $O(N)$ 計算出答案。

## pC - 很多區間最小值總和問題

### 題意

給予兩個正整數 $N, M$，代表所有長度為 $N$ 的正整數數列 $(A_1, A_2, A_3, ... , A_N)$ 符合 $1 ≤ A_i ≤ M (1 ≤ i ≤ N)$ ，總共有 $M^N$ 個滿足此條件且相異的數列，請你求這 $M^N$ 個數列對於 **區間最小值總和問題(也就是pA)** 的答案總和，因為答案可能很大，請模 $998244353$ 。

### 暴力

如果照題目直接的做，枚舉所有的 $A$ ，根據 $\text{pA}$ 的 $O(N)$ 的方法，可以做到 $O(M^N \cdot N)$ 的複雜度，雖然這東西顯然沒辦法通過，但可以利用小的 $(N,M)$拿來觀察規律。

### 另一種思路

如果我們不計算 $M^N$ 個序列，而是計算答案是 $i$ 的數列有幾個，我們以 $cnt_{i,j}$ 代表答案是 $i$ ，區間長度 $j$ 的數列有幾個，那我們可以推得以下關係 :
$cnt_{i,j} = (n-j+1) \times m^{(n-j+1)} \times ((m-i+1)^j-(m-i)^j)$

前面的 $n-j+1$ 是因為如果整個序列長度是 $N$，那長度是 $j$ 的部分會被算 $n-j+1$ 次，因為有區間 $[1,j], [2,j+1], ..., [n-j+1,n]$，總共是$n-j+1$個。而$m^{(n-j+1)}$是剩下不在範圍內可以隨便填的地方，因為剩下 $n-j+1$格，每格可以填 $1 \sim M$，所以有 $m^{(n-j+1)}$ 填法。

最後的 $(m-i+1)^j-(m-i)^j$ 是討論區間內可以填甚麼數字，如果答案是 $i$ 的話，可以填的數字一定要是 $i$ (含)以上，也就是 $i,i+1,i+2,...,M$ 這些，所以有 $(m-i+1)^j$ 種選擇，然而不能全部數字都是 $i+1$ (含)以上，所以要扣除 $(m-i)^j$。

### 分析

答案的話其實就是 $\sum_{i=1}^M \sum_{j=1}^N i \times cnt_{i,j}$，這裡可以做到 $O((NM)w)$，其中 $O(w)$ 根據實作方法而改變，有可能是 $O(logN)$ ，但其實可以做到 $O(1)$。

### 進一步優化

$O((NM)w)$ 雖然比起之前的 $O(M^N \cdot N)$ 好很多，但他當然還是不夠快，所以我們要繼續優化他

我們固定一個 $j$ 值(下圖令 $j=1$)，然後看他所有的 $i$ ，會長成這樣 :


答案就是表格裡面的數乘上左邊及上面的數，先把上面的數提出來，下面變成 :

$\sum_{i=1}^m i \times (m-i+1)^x-(m-i)^x$

然後我們發現一項的 $(m-i+1)$ 的部分跟下一項 $i$ 的 $(m-i)^x$ 的部分是同個東西，然後前面 $i$ 多了 $1$ ，所以其實 $\sum_{i=1}^m i \times (m-i+1)^x-(m-i)^x = \sum_{i=1}^m i^x$。

那我們怎麼快速的求 $\sum_{x=1}^n\sum_{i=1}^m i^x \times (n-x+1) \times m^{(n-x+1)}$ 呢? 其實我目前沒有想法，但是我們可以往另一個維度的方向看，變成求 $\sum_{x=1}^m \sum_{i=1}^n x^i \times (n-i+1) \times m^{(n-i+1)}$，可以把 $x^i \times m^{(n-i+1)}$看成一個部分，先無視 $(n-i+1)$，那他其實是一個公比 $r = \frac{x}{m}$ 的等比數列，可以用等比級數求和，$(n-i+1)$的部分可以看成有 $N$ 個這樣的等比數列，第 $L$ 個的長度為 $L$，把他們全部加起來，就會變成我們要的樣子，而這要怎麼加起來呢 ? 我們發現等比級數和的公式中的 $r^n-1$ 這個部分的 $r^n$，因為 $L = {1,2,3,.. ,N}$，所以其實這又是一個等比級數，所以又可以用等比級數求和 !

最終此問題可以以 $O(M \times (logN + log mod))$ 求出答案，其中 $mod = 998244353$ 。

另外 oier_without_op 提到的，pC 能不能做到 $O(N)$ 之類的複雜度，就是上面提的快速計算 $x=1,2,...,N$ 的 $\sum_{i=1}^m i^x$ 的值，這目前不知道有沒有解。