第一屆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\le {10}^6$ ，可以說是幾乎不可能通過。

$O(N)$ 的優化

如果我們窮舉

$R$ ，有沒有辦法移動一格就

$O(1)$ 算出區間

$[1,R],[2,R],...,[R,R]$ 的答案呢? 其實是可以的，我們發現從右到左，

$\text{MIN}$的值其實是單調的，所以可以使用單調堆疊 (monotone stack)，紀錄兩個元素

$(x,y)$，代表大小和區間長度，如果現在插入的元素

$\ge$ 棧頂的大小，那就

$\text{push}$ 一個新的進去，否則就

$\text{pop}$ 出來 (代表答案變小)，計算「被變小」多少，之後把這些區間合併成一個新的，放一個新的進去，時間複雜度為

$O(N)$。

另外這題似乎也有很多

$O(NlogN)$ 的作法，如果常數不大應該也會通過。

pB - 尼姆樹

題意

給你

$N$ 個點、帶邊權的樹

$T$，有兩個人要在

$T$ 上玩遊戲，一開始

$1$ 上面放了一個棋子，兩個人輪流進行操作，每一個操作是選擇任何一個在棋子目前位置周遭邊權

$>0$ 的邊，把棋子移到邊上另一頭的點，並選擇任何小於等於該邊邊權的正整數

$x$，把剛剛經過的邊權減少

$x$，不停輪流操作直到某一方無法進行任何操作結束，我們定義進行最後一個操作的人獲勝。請問，如果兩個人使用最佳策略，那最終是誰會獲勝?

我們可以先想想看如果邊權都是

$1$ 會如何。

$W_i=1$

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

如果邊權都是

$1$，我們可以把他想像成一個有方向的邊 (因為一定只能從起點那邊走過來，然後不能走回去) ，而最下面的葉節點，踩到那點的人就輸了，例如上圖的點

$3,5$，我們可以定義

$d{p}_v$ 代表踩到

$v$ 的人最後會贏/輸，接著可以透過他的子節點的

$d{p}^{\prime }$ 做計算，轉移式是 : 因為下面的是對手的，如果至少有一個

$d{p}^{\prime }$ 是輸的，那

$d{p}_v$ 就會是贏，否則

$d{p}_v$ 會輸。

我們定義把全部邊權改成

$1$ 的樹叫做

$T^{\prime }$。

$W_i\ne 1$

接著我們回來討論我們想要的，

$T$ 的答案，我們一樣定義

$dp$ ，對一個決策點

$v$ ，假設我們知道

$v$ 以下的子樹的結果，如果

$d{p}_v$ 是贏的，那他明顯會走向會讓他贏的點，也就是

$d{p}^{\prime }$ 是輸的點，並且直接把邊走完。

如果

$d{p}_v$ 是輸的，因為隨便選一個點下走，不論有沒有把邊權用光都沒差，在子節點上，另一個人(會贏的)肯定會繼續往下走並且走完，所以其實

$T$ 的答案和

$T^{\prime }$ 一樣。

我們可以透過

$\text{dfs}$ 以

$O(N)$ 計算出答案。

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

題意

給予兩個正整數

$N,M$，代表所有長度為

$N$ 的正整數數列

$(A_1,A_2,A_3,...,A_N)$ 符合

$1\le A_i\le M(1\le i\le N)$ ，總共有

$M^N$ 個滿足此條件且相異的數列，請你求這

$M^N$ 個數列對於 區間最小值總和問題(也就是pA) 的答案總和，因為答案可能很大，請模

$998244353$ 。

暴力

如果照題目直接的做，枚舉所有的

$A$ ，根據

$\text{pA}$ 的

$O(N)$ 的方法，可以做到

$O(M^N\cdot N)$ 的複雜度，雖然這東西顯然沒辦法通過，但可以利用小的

$(N,M)$拿來觀察規律。

另一種思路

如果我們不計算

$M^N$ 個序列，而是計算答案是

$i$ 的數列有幾個，我們以

$cn{t}_{i,j}$ 代表答案是

$i$ ，區間長度

$j$ 的數列有幾個，那我們可以推得以下關係 :

$cn{t}_{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 cn{t}_{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+logmod))$ 求出答案，其中

$mod=998244353$ 。

另外 oier_without_op 提到的，pC 能不能做到

$O(N)$ 之類的複雜度，就是上面提的快速計算

$x=1,2,...,N$ 的

$\sum _{i=1}^m{i}^x$ 的值，這目前不知道有沒有解。