這題感覺我的作法爛爛的，建議先理解官方解還有dreamoon的code，都寫的蠻清楚的@@
作法：
首先考慮一個會有問題的作法：對於每個點，往他上下左右四個方向最近的點分別連一條邊（如果沒有點就不用連），然後直接對這張圖二塗色。而這樣隨便都能構一個出現奇環的測資讓他爛掉，因此我們可以考慮先把圈都拔光，具體來說，我們考慮一種比較特別的圈，如果沿著這樣的圈一直走的話，走的方向依序是「橫直橫直......」，也就是每走一個點都會轉$90$度。顯然這樣的圈的點數為偶數，那麼沿著這個圈一路途上紅藍交錯的顏色，就可以把這個圈上的所有點砍掉了，因為塗完後他讓每條鉛直線和水平線上的紅藍點數增加的個數相同。因此只要把這種圈都砍完之後，剩下的圖就可以用剛才提到的那個演算法了：直接把圖建出來二塗色，因為此時已經沒有圈了（容易證明，當不存在剛才那種「特別的圈」時，原本的圖裡也不會有圈），所以直接塗就可以了。
所以重點在於要如何找圈然後把他拔掉，首先考慮直接DFS的算法，也就是走到一個點的時候，考慮所有和他同行（或同列，只會是其中一個，因為我們要找的是剛才提到的特別的圈）的點DFS下去，當找到一條回邊，也就是形成了一個圈時，就沿著父親一直走上去，並沿路塗色，塗完後直接中斷這次的DFS，一直 return 回去直到當前的點的答案還沒被決定為止，然後之後在DFS的時候就可以完全無視那些已經被塗過色的點了。這個算法還有需要注意的地方，因為當我們最一開始DFS的時候一定是先選一個方向去DFS，也就是假設從這個點出發是先走橫的，這樣之後DFS的過程就知道現在這個點的下一步是走橫的還是直的。而如果結束DFS的時候根節點還沒有被塗色，就要去DFS起點是走直的的情況，否則之後在以其他點當根DFS的時候，當戳到了這個還沒被塗色的舊根節點時會誤以為這是一條回邊，這時沿著父親走就會爛掉。
顯然這個算法複雜度會爛掉，於是我只好用 linked list 優化 DFS ，這東西在TIOJ 1220也有用到類似的東西（雖然我當時的解不是那樣做的），具體來說就是：對每個$x$座標維護一條 linked list ，代表當前的$x$座標等於他的點中還剩下這些點。對每個$y$座標一樣也有一條 linked list 。由這裡可以看出每個原圖中的點$P$會對應到兩個在 linked list 中的節點$nx,ny$（其中$nx$是被放在「$x$座標的lonked list」中的節點，$ny$則是$y$座標的），並且讓$nx$代表走到$P$時下一步是要走鉛直方向的，$ny$則是代表走到$P$時下一步是要走水平方向的。
建好 linked list 後就可以DFS了，當走到一個點$P$時，假設他現在要走的是直的方向，那麼就先把他對應的$nx$拔掉，然後去他的$x$座標這條 linked list 裡找後繼節點，當找到一個後繼節點$Q$時就直接把$Q$對應的$nx$拔掉再DFS下去，一樣當找到一個圈的時候就一樣沿路塗色並一直 return 。但這樣做會有問題，會發現根本找不到圈，因為當一個點被走到時他所對應的$nx,ny$都已經被拔掉了，之後當然就不會有任何邊走向他了。解決方法是當在DFS時，假設現在是$P$找到了他的後繼節點$Q$（和剛剛一樣），那麼在DFS下去之前先不要把$Q$的$nx$拔掉，等到DFS出來之後再拔掉，因為如果有圈形成的話他的回邊一定是連向$Q$的$nx$的。最後還要注意到剛才用 linked list 優化之前的那個細節，也就是根節點要記得擴展完，因此當最一開始DFS進去是選$x$方向的 linked list 的話，出來之後發現根節點還沒被塗色，就要試試看選$y$方向的。
code :
2015年5月31日 星期日
[CF 547C] Mike and Foam
作法：
首先可以把問題化為：支援一個資料結構，可以加入和刪除數，並且詢問目前裡面有幾個數和給定的某個數互質。設當前詢問的數是$x$，其因數由為$d_1,...,d_r$，那麼$x$和所有當前裡面的數的 gcd 值只有可能是$x$的因數，因此設目前總共有$a_i$的數和$x$的 gcd 等於$i$，則只有$x$的因數的$a$值非$0$，而我們想求的就是$a_1$。單一個$a_i$的值不容易求，但如果令$num_i$代表目前這些數裡面有幾個數是$i$的倍數，顯然可以在加入和刪除一個數時維護好$num_i$的陣列，那麼考慮$num_{d_i}$，他其實就會等於所有滿足$d_i | d_j$ 的$a_{d_j}$ 的總和，也就是如果令$A_i=\{ d_j | d_j\%d _i=0 \}$，那麼$\displaystyle num_{d_i}=\sum_{t\in A_i}a_t$，因此現在要用已知的$num_{d_i}$們的式子來求出$a_1$。再來就有點類似莫比烏斯反演的概念了，那東西的詳細可以參考維基，其實和這題一樣本質上來說就是排容原理。不妨設$d_1,...,d_k$就是$x$的所有質因數（不包含$1$），那麼考慮集合$A_1,...,A_k$，跟他們的宇集$\{ d_1,...,d_r \}$，並且以下記$|S|$代表$S$中所有元素的$a$值的和。可以得到$A_1\bigcup A_2\bigcup ... \bigcup A_k$包含了所有$x$的非$1$的因數，因此用宇集扣掉他之後就只剩下$1$，也就是我們要求扣掉之後的集合內元素的權值和（雖然他只有一個元素）。這時就可以用排容了，首先宇集的權值和就是$num_1$，再來要扣掉$|A_1|,...,|A_k|$，由上面的結論可以知道$|A_i|$就是$num_{d_i}$，直接代入即可。再來要加回長的像$|A_i\bigcap A_j|$的這種東西，這裡就是莫比烏斯變換關鍵的地方，因為$d_i$和$d_j$是兩個$x$的不同的質因數，所以他們互質，而回到$A_i$的定義，他裡面蒐集了所有是$d_i$倍數的$x$的因數，所以由$d_i,d_j$互質就可以得到$|A_i\bigcap A_j|=num_{i\cdot j}$，因為他們的交集就代表著滿足他是$d_i,d_j$倍數的$x$的因數，所以是滿足他是$d_i\cdot d_j$倍數的$x$的因數，所以就可以化簡成$num_{i\cdot j}$了。到了好幾個$A$交集在一起時一樣可以融合起來變成一個$num$值，於是這樣就成功求出答案了。
而實作的方法又轉了個彎，因為注意到上面那條式子裡面，我們會用到的$num$值的下標都是「沒有平方因子的數」(square-free)，或是說把他質因數分解的話會分成好幾個不同的質數的一次方相乘，而$num$值前面的係數則和當前下標的質因數個數有關，若個數為奇數則為$-1$，若為偶數則為$1$，這東西就是莫比烏斯函數，因此在計算上我們只要先把$x$的所有因數找出來，求出所有因數的$num$值乘上其莫比烏斯函數的值的總和就可以了。
code :
首先可以把問題化為：支援一個資料結構，可以加入和刪除數，並且詢問目前裡面有幾個數和給定的某個數互質。設當前詢問的數是$x$，其因數由為$d_1,...,d_r$，那麼$x$和所有當前裡面的數的 gcd 值只有可能是$x$的因數，因此設目前總共有$a_i$的數和$x$的 gcd 等於$i$，則只有$x$的因數的$a$值非$0$，而我們想求的就是$a_1$。單一個$a_i$的值不容易求，但如果令$num_i$代表目前這些數裡面有幾個數是$i$的倍數，顯然可以在加入和刪除一個數時維護好$num_i$的陣列，那麼考慮$num_{d_i}$，他其實就會等於所有滿足$d_i | d_j$ 的$a_{d_j}$ 的總和，也就是如果令$A_i=\{ d_j | d_j\%d _i=0 \}$，那麼$\displaystyle num_{d_i}=\sum_{t\in A_i}a_t$，因此現在要用已知的$num_{d_i}$們的式子來求出$a_1$。再來就有點類似莫比烏斯反演的概念了，那東西的詳細可以參考維基，其實和這題一樣本質上來說就是排容原理。不妨設$d_1,...,d_k$就是$x$的所有質因數（不包含$1$），那麼考慮集合$A_1,...,A_k$，跟他們的宇集$\{ d_1,...,d_r \}$，並且以下記$|S|$代表$S$中所有元素的$a$值的和。可以得到$A_1\bigcup A_2\bigcup ... \bigcup A_k$包含了所有$x$的非$1$的因數，因此用宇集扣掉他之後就只剩下$1$，也就是我們要求扣掉之後的集合內元素的權值和（雖然他只有一個元素）。這時就可以用排容了，首先宇集的權值和就是$num_1$，再來要扣掉$|A_1|,...,|A_k|$，由上面的結論可以知道$|A_i|$就是$num_{d_i}$，直接代入即可。再來要加回長的像$|A_i\bigcap A_j|$的這種東西，這裡就是莫比烏斯變換關鍵的地方，因為$d_i$和$d_j$是兩個$x$的不同的質因數，所以他們互質，而回到$A_i$的定義，他裡面蒐集了所有是$d_i$倍數的$x$的因數，所以由$d_i,d_j$互質就可以得到$|A_i\bigcap A_j|=num_{i\cdot j}$，因為他們的交集就代表著滿足他是$d_i,d_j$倍數的$x$的因數，所以是滿足他是$d_i\cdot d_j$倍數的$x$的因數，所以就可以化簡成$num_{i\cdot j}$了。到了好幾個$A$交集在一起時一樣可以融合起來變成一個$num$值，於是這樣就成功求出答案了。
而實作的方法又轉了個彎，因為注意到上面那條式子裡面，我們會用到的$num$值的下標都是「沒有平方因子的數」(square-free)，或是說把他質因數分解的話會分成好幾個不同的質數的一次方相乘，而$num$值前面的係數則和當前下標的質因數個數有關，若個數為奇數則為$-1$，若為偶數則為$1$，這東西就是莫比烏斯函數，因此在計算上我們只要先把$x$的所有因數找出來，求出所有因數的$num$值乘上其莫比烏斯函數的值的總和就可以了。
code :
2015年5月30日 星期六
[CF 487E] Tourists
作法：
這題的官方解大部份講的蠻清楚的，主要就是要先知道那個引理，然後把原圖的BCC樹建出來，對每塊縮完後的BCC（或是單一一個割點）維護那塊目前的最小值，然後對BCC樹作樹鍊剖分，讓他可以支援「修改點權與詢問某條路徑上點權最小值」這兩件事。但官方解裡提到的「只要更新其祖先的那塊BCC的值就好了」寫的不太清楚，這裡詳細解釋一下。
以下圖舉例，右邊是用BCC縮完點後的圖，其中紅色是割點，黑色的是一塊BCC。對於每個BCC都維護一個 multiset ，裡面裝的值是「在這個BCC內的點，除了他的祖先以外的所有點的值」，並且這坨BCC在新的樹當中的「點權」就會是這個 multiset 裡最小的數，割點在新的樹裡的點權則和原圖中的一樣。例如在下圖中，$2,3,4,5$這坨BCC在新的圖中他的點權就會是$2,3,4$的點權的最小值，$2,6,7$那坨則是$6,7$點權的最小值，其他以此類推。這樣就能在$O(logn)$的時間內完成修改了。具體方法是，如果改的點是割點的話，會動到的新圖中的點權有割點本身，還有他的父親BCC（如果他有父親的話一定是一坨BCC）。而如果改的點不是割點的話就只會動到他所屬的BCC的權值而已。
code :
這題的官方解大部份講的蠻清楚的，主要就是要先知道那個引理，然後把原圖的BCC樹建出來，對每塊縮完後的BCC（或是單一一個割點）維護那塊目前的最小值，然後對BCC樹作樹鍊剖分，讓他可以支援「修改點權與詢問某條路徑上點權最小值」這兩件事。但官方解裡提到的「只要更新其祖先的那塊BCC的值就好了」寫的不太清楚，這裡詳細解釋一下。
以下圖舉例，右邊是用BCC縮完點後的圖，其中紅色是割點，黑色的是一塊BCC。對於每個BCC都維護一個 multiset ，裡面裝的值是「在這個BCC內的點，除了他的祖先以外的所有點的值」，並且這坨BCC在新的樹當中的「點權」就會是這個 multiset 裡最小的數，割點在新的樹裡的點權則和原圖中的一樣。例如在下圖中，$2,3,4,5$這坨BCC在新的圖中他的點權就會是$2,3,4$的點權的最小值，$2,6,7$那坨則是$6,7$點權的最小值，其他以此類推。這樣就能在$O(logn)$的時間內完成修改了。具體方法是，如果改的點是割點的話，會動到的新圖中的點權有割點本身，還有他的父親BCC（如果他有父親的話一定是一坨BCC）。而如果改的點不是割點的話就只會動到他所屬的BCC的權值而已。
code :
[CF 487D] Conveyor Belts
作法：
因為他的輸送帶的方向只有左右上，所以分塊顯然可以做，只是複雜度有點高。官方解中提到的線段樹的作法沒有寫的很清楚，這裡詳細講一下。
假設線段樹的某個節點的區間為$[L,R]$，則這個節點裡放的資訊為：考慮$(L,1),(R,m)$形成的矩形，則從每個$x$座標為$R$的格子開始走，走出這塊矩形時的第一個格子是哪格，或是會形成無窮回圈。也就是這個節點裡存了$m$個格子的座標（所以是$m$個pair）。那麼就可以由$[a,b]$和$[b+1,c]$的資訊推出$[a,c]$的資訊了，因此可以用線段樹把每個節點的資訊都先處理好。至於如何回答詢問，假設詢問的點為$(x,y)$首先把線段$[1,x]$用線段樹拆解成好幾個線段，那麼只要從最後一個拆出來線段開始，利用線段樹上已經處理好的資訊就可以直接跳到下一個線段的起點$x$座標，或是得知他會走出左右邊界，或是形成無窮回圈了。而修改是顯然的。
code :
因為他的輸送帶的方向只有左右上，所以分塊顯然可以做，只是複雜度有點高。官方解中提到的線段樹的作法沒有寫的很清楚，這裡詳細講一下。
假設線段樹的某個節點的區間為$[L,R]$，則這個節點裡放的資訊為：考慮$(L,1),(R,m)$形成的矩形，則從每個$x$座標為$R$的格子開始走，走出這塊矩形時的第一個格子是哪格，或是會形成無窮回圈。也就是這個節點裡存了$m$個格子的座標（所以是$m$個pair）。那麼就可以由$[a,b]$和$[b+1,c]$的資訊推出$[a,c]$的資訊了，因此可以用線段樹把每個節點的資訊都先處理好。至於如何回答詢問，假設詢問的點為$(x,y)$首先把線段$[1,x]$用線段樹拆解成好幾個線段，那麼只要從最後一個拆出來線段開始，利用線段樹上已經處理好的資訊就可以直接跳到下一個線段的起點$x$座標，或是得知他會走出左右邊界，或是形成無窮回圈了。而修改是顯然的。
code :
2015年5月27日 星期三
[CF 491C] Deciphering
作法：
首先遇處理出把每個字母換成另外一個字母的$k\cdot k$種可能，算出他可以得幾分，那麼這樣就可以轉換成新的問題：有$k$個點，任兩個點之間都連一條有向邊，並且每條有向邊都有權重，對每個點都選一條起點為他的有向邊，滿足每個點恰被當成選到的邊的終點一次，求這些邊的總和的最大值。而這就是經典的二分圖最大權完美匹配問題，因為「對每個點選唯一的要走到的點」就類似於對每個點選一個匹配點。構造新的圖為左右分別有$k$個點，並且如果原圖中$i$連到$j$的權重為$w$，則在左邊第$i$個點和右邊第$j$個點之間連權重$w$的邊，求最大權完美匹配就是答案了。
首先遇處理出把每個字母換成另外一個字母的$k\cdot k$種可能，算出他可以得幾分，那麼這樣就可以轉換成新的問題：有$k$個點，任兩個點之間都連一條有向邊，並且每條有向邊都有權重，對每個點都選一條起點為他的有向邊，滿足每個點恰被當成選到的邊的終點一次，求這些邊的總和的最大值。而這就是經典的二分圖最大權完美匹配問題，因為「對每個點選唯一的要走到的點」就類似於對每個點選一個匹配點。構造新的圖為左右分別有$k$個點，並且如果原圖中$i$連到$j$的權重為$w$，則在左邊第$i$個點和右邊第$j$個點之間連權重$w$的邊，求最大權完美匹配就是答案了。
code :
[CF 494E] Sharti
作法：
詳細的作法在官方解已經講的很清楚了，這裡講一下為什麼 grundy number 長那樣的證明。
首先考慮$k$是無限大的情形，也就是這個遊戲可以選擇任意大的正方形，我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的，以下用數學歸納法，假設以$(1,1)$為左上角，$(x,y)$為右下角的矩形中，除了$(x,y)$以外的格子的 grundy number 都知道了，並且設$(x,y)$這格的理論值為$2^i$，那麼我們要證明兩件事：「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$，還有有出現$0,1,...,2^i-1$。
首先是沒有出現$2^i$，因為他的後繼狀態是一個正方形的每格裡都有一個石頭，除了$(x,y)$那格，因此這個命題就可以等價為：考慮一張方格表，上面寫上每個格子的理論上的 grundy number ，則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法，如果某一塊正方形內所有的數 xor 起來等於$0$，因為格子中的數都是$2$的冪次，所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$，設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量，那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$，而因為對於每個$i$，這塊正方形中的$2^i$都是偶數個，所以所有$a_i$的奇偶性相同，當$i$足夠大時$a_i$顯然$=0$，因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$，其中$y$是奇數，那麼不難證明$a_y$是奇數，矛盾。
再來是證明出現了$0,1,...,2^i-1$（其中$0$是顯然的），這可以用數歸解決，假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的，那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊，那麼對於任意一個落在左下角那塊的格子$(x,y)$來說，考慮$(x-2^r,y)$，可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達，所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理，除了$(2^{r+1},2^{r+1})$這一格，我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時，因為整張表格是沿對角線對稱的，所以兩邊的 xor 值會抵消，只剩下對角線上的，此時就化為一維的問題了，也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話，令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$，則$S$裡出現了$1,2,...,2^{r+1}-1$（其中$\bigoplus $代表 xor 運算）。這件事的證明可以對$r$數歸，還算蠻顯然的所以略去，因此這樣成功證完$k$是無限大的情形了。
當$k$不是無限大時其實也類似，一樣也是先考慮每個格子的理論值形成的表，證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是，假設$t$滿足$2^t\leq k<2^{t+1}$，那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的，證法和剛才類似，這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了，因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格，所以顯然是對的。
code :
詳細的作法在官方解已經講的很清楚了，這裡講一下為什麼 grundy number 長那樣的證明。
首先考慮$k$是無限大的情形，也就是這個遊戲可以選擇任意大的正方形，我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的，以下用數學歸納法，假設以$(1,1)$為左上角，$(x,y)$為右下角的矩形中，除了$(x,y)$以外的格子的 grundy number 都知道了，並且設$(x,y)$這格的理論值為$2^i$，那麼我們要證明兩件事：「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$，還有有出現$0,1,...,2^i-1$。
首先是沒有出現$2^i$，因為他的後繼狀態是一個正方形的每格裡都有一個石頭，除了$(x,y)$那格，因此這個命題就可以等價為：考慮一張方格表，上面寫上每個格子的理論上的 grundy number ，則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法，如果某一塊正方形內所有的數 xor 起來等於$0$，因為格子中的數都是$2$的冪次，所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$，設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量，那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$，而因為對於每個$i$，這塊正方形中的$2^i$都是偶數個，所以所有$a_i$的奇偶性相同，當$i$足夠大時$a_i$顯然$=0$，因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$，其中$y$是奇數，那麼不難證明$a_y$是奇數，矛盾。
再來是證明出現了$0,1,...,2^i-1$（其中$0$是顯然的），這可以用數歸解決，假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的，那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊，那麼對於任意一個落在左下角那塊的格子$(x,y)$來說，考慮$(x-2^r,y)$，可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達，所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理，除了$(2^{r+1},2^{r+1})$這一格，我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時，因為整張表格是沿對角線對稱的，所以兩邊的 xor 值會抵消，只剩下對角線上的，此時就化為一維的問題了，也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話，令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$，則$S$裡出現了$1,2,...,2^{r+1}-1$（其中$\bigoplus $代表 xor 運算）。這件事的證明可以對$r$數歸，還算蠻顯然的所以略去，因此這樣成功證完$k$是無限大的情形了。
當$k$不是無限大時其實也類似，一樣也是先考慮每個格子的理論值形成的表，證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是，假設$t$滿足$2^t\leq k<2^{t+1}$，那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的，證法和剛才類似，這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了，因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格，所以顯然是對的。
code :
2015年5月25日 星期一
[CF 494D] Birthday
作法：
首先觀察到我們有兩種方法來計算題目所求的值，令$ \displaystyle g(u)=\sum_{i=1}^{n} d(u,i)^2 $，那麼$\displaystyle f(u,v)=g(u)-2\cdot \sum_{x\notin S(v)} d(u,x)^2=2\cdot \sum_{x\in S(v)} d(u,x)^2 - g(u)$
首先先想辦法求出$g(u)$，如果我們只要知道特定一個$u$的$g$值的話，就直接對以$u$為根建立有根樹並DP就好了，DP時對每個節點$x$紀錄三個值：以$x$為根的子樹的大小，以$x$為根的子樹中的所有點走到$x$的距離和，還有以$x$為根的子樹中的所有點走到$x$的距離平方和，這三個東西的遞推式子算是顯然的（以後簡稱他們叫作三個DP值）。但我們需要對每個$u$都算出他的$g$值，如果對每個點都DFS一次顯然會太慢。這時只要注意到，實際上對兩個不同的點DFS的時候，會有很多點的那三個值是一模一樣的，更具體來說，如果現在對$X$和$Y$作DFS，那麼對於任何一個點$u$，如果從$X$走到$u$的路徑上的最後一條邊等於從$Y$走到$u$的路徑上的最後一條邊，則兩次的DFS在$u$求出的值是一樣的，因為這兩次的$u$的子樹是一模一樣的。這啟發了我們可以對每個點分別計算「當他的父節點是他的某個鄰居時，他的三個DP值會是多少」。嚴謹來說，定義對於相鄰的兩點$u,v$，定義$T(u,v)$代表砍掉$(u,v)$這條邊後以$u$為根的子樹，那麼把這棵子樹對應的三個DP值算出來。這樣只有$O(n)$個值要算，並且也不難得知這些值的$O(n)$或是$O(nlogn)$的算法，因此這裡成功解決了遇處理每個點的$g$值的部份。
有了每個點的$g$值之後，再回到題目要求的式子。當$u$不在以$v$為根的子樹內時，那麼第二條和所求等價的式子會很好算，因為我們可以把$d(u,x)$拆成$d(u,v)+d(v,x)$，這樣所求就可以由剛才求出的$T(v,fa[v])$的三個DP值計算出來了，其中$fa[v]$代表$v$的父節點（題目給的是以$1$為根的有根樹）。至於$u$落在$v$的子樹內的情形則使用第一條和所求等價的式子，此時對應的子樹就會是$T(fa[v],v)$，因此算法也根剛才類似了。另外注意到這個算法的回答詢問複雜度會是$O(logn)$，因為會需要求兩點之間的距離。
code :
首先觀察到我們有兩種方法來計算題目所求的值，令$ \displaystyle g(u)=\sum_{i=1}^{n} d(u,i)^2 $，那麼$\displaystyle f(u,v)=g(u)-2\cdot \sum_{x\notin S(v)} d(u,x)^2=2\cdot \sum_{x\in S(v)} d(u,x)^2 - g(u)$
首先先想辦法求出$g(u)$，如果我們只要知道特定一個$u$的$g$值的話，就直接對以$u$為根建立有根樹並DP就好了，DP時對每個節點$x$紀錄三個值：以$x$為根的子樹的大小，以$x$為根的子樹中的所有點走到$x$的距離和，還有以$x$為根的子樹中的所有點走到$x$的距離平方和，這三個東西的遞推式子算是顯然的（以後簡稱他們叫作三個DP值）。但我們需要對每個$u$都算出他的$g$值，如果對每個點都DFS一次顯然會太慢。這時只要注意到，實際上對兩個不同的點DFS的時候，會有很多點的那三個值是一模一樣的，更具體來說，如果現在對$X$和$Y$作DFS，那麼對於任何一個點$u$，如果從$X$走到$u$的路徑上的最後一條邊等於從$Y$走到$u$的路徑上的最後一條邊，則兩次的DFS在$u$求出的值是一樣的，因為這兩次的$u$的子樹是一模一樣的。這啟發了我們可以對每個點分別計算「當他的父節點是他的某個鄰居時，他的三個DP值會是多少」。嚴謹來說，定義對於相鄰的兩點$u,v$，定義$T(u,v)$代表砍掉$(u,v)$這條邊後以$u$為根的子樹，那麼把這棵子樹對應的三個DP值算出來。這樣只有$O(n)$個值要算，並且也不難得知這些值的$O(n)$或是$O(nlogn)$的算法，因此這裡成功解決了遇處理每個點的$g$值的部份。
有了每個點的$g$值之後，再回到題目要求的式子。當$u$不在以$v$為根的子樹內時，那麼第二條和所求等價的式子會很好算，因為我們可以把$d(u,x)$拆成$d(u,v)+d(v,x)$，這樣所求就可以由剛才求出的$T(v,fa[v])$的三個DP值計算出來了，其中$fa[v]$代表$v$的父節點（題目給的是以$1$為根的有根樹）。至於$u$落在$v$的子樹內的情形則使用第一條和所求等價的式子，此時對應的子樹就會是$T(fa[v],v)$，因此算法也根剛才類似了。另外注意到這個算法的回答詢問複雜度會是$O(logn)$，因為會需要求兩點之間的距離。
code :
2015年5月23日 星期六
[CF 497E] Subsequences Return
作法：
這題的官方解中已經把前面DP的部份講的很清楚了，這裡紀錄一下後面我在求那些矩陣的方法，和官方解的不太一樣。首先$A_{0,x}$是顯然的，也就是最原始的轉移，他會是一個對角線上都是$1$，還有上面數來第$x$列都是$1$的矩陣。再來我們要想辦法在比較快的時間內求出$A_{m,x}$，首先我們知道$A_{m,0}=A_{m-1,0}\times A_{m-1,1}\times ... \times A_{m-1,k-1}$，還有$A_{m,1}=A_{m-1,1}\times A_{m-1,2}\times ... \times A_{m-1,k-1}\times A_{m-1,0}$，觀察這兩條式子可以發現他們只差在前後的$A_{m-1,0}$，也就是如果我們預先算好了$A_{m-1,0}$的反矩陣$I_{m-1,0}$的話，就可以直接用$O(k^3)$的時間從$A_{m,0}$算出$A_{m,1}$了，因此我們再對每個$A_{m,x}$紀錄他的反矩陣$I_{m,x}$就可以了，並且其遞推式和$A$的遞推式很像。至於邊界的部份（也就是$I_{0,x}$）其實長的也蠻好看的，因為$A_{0,x}$的樣子很特殊。可以得到$I_{0,x}$的樣子是：在主對角線上都是$1$，而在上面數來第$x$排的每個數，除了主對角線上的那個數是$1$以外都是$-1$（記得在賦值時要寫$MOD-1$）。
code :
這題的官方解中已經把前面DP的部份講的很清楚了，這裡紀錄一下後面我在求那些矩陣的方法，和官方解的不太一樣。首先$A_{0,x}$是顯然的，也就是最原始的轉移，他會是一個對角線上都是$1$，還有上面數來第$x$列都是$1$的矩陣。再來我們要想辦法在比較快的時間內求出$A_{m,x}$，首先我們知道$A_{m,0}=A_{m-1,0}\times A_{m-1,1}\times ... \times A_{m-1,k-1}$，還有$A_{m,1}=A_{m-1,1}\times A_{m-1,2}\times ... \times A_{m-1,k-1}\times A_{m-1,0}$，觀察這兩條式子可以發現他們只差在前後的$A_{m-1,0}$，也就是如果我們預先算好了$A_{m-1,0}$的反矩陣$I_{m-1,0}$的話，就可以直接用$O(k^3)$的時間從$A_{m,0}$算出$A_{m,1}$了，因此我們再對每個$A_{m,x}$紀錄他的反矩陣$I_{m,x}$就可以了，並且其遞推式和$A$的遞推式很像。至於邊界的部份（也就是$I_{0,x}$）其實長的也蠻好看的，因為$A_{0,x}$的樣子很特殊。可以得到$I_{0,x}$的樣子是：在主對角線上都是$1$，而在上面數來第$x$排的每個數，除了主對角線上的那個數是$1$以外都是$-1$（記得在賦值時要寫$MOD-1$）。
code :
[CF 497D] Gears
作法：
當兩個多邊形碰撞時，一定是一個多邊形的其中一個頂點碰到另一個多邊形的線段，並且顯然當有頂點碰到別人的線段時他們一定相撞了。因此我們只要對兩個多邊形的其中一個枚舉頂點，另一個枚舉邊，然後想辦法$O(1)$判斷這個點會不會跑到這條線段上就可以了。這裡要用相對運動來看會好做很多。假設現在要判斷的是$A$上的一條線段和$B$上的一個頂點$X$是否會在運動的時候碰到，想像站在$P$點看所有東西，並且面對的方向是跟著$A$一起轉的，也就是當$A$順時針旋轉了$\theta $度之後面對的方向也跟著順時針轉$\theta $度，那麼我們看到的$A$上的這條線段會是永遠不動的。設時間$0$時$Q$的座標為$(a,b)$，$X$的座標為$(x,y)$，那麼可以知道$X$被旋轉了$\theta $度之後他在時間$0$的座標系上的座標會是$M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix}$，其中$M_{\theta}$代表的是可以將一個點以原點為中心逆時針旋轉$\theta $的矩陣。但此時我們的座標系已經順時針旋轉$\theta $度了，所以這時候看到的$X$點的座標必須要逆時針旋轉$\theta $度才是對的，也就是等於$M_{\theta}(M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix})=\begin{bmatrix}x-a\\y-b\end{bmatrix}+M_{\theta}\begin{bmatrix}a\\ b\end{bmatrix}$，由這個式子就可以看出這是一個以$(x-a,y-b)$為圓心，半徑為$\sqrt{a^2+b^2}$的圓了，因此只要寫個線段和圓是否有相交的函式就可以了。
code :
當兩個多邊形碰撞時，一定是一個多邊形的其中一個頂點碰到另一個多邊形的線段，並且顯然當有頂點碰到別人的線段時他們一定相撞了。因此我們只要對兩個多邊形的其中一個枚舉頂點，另一個枚舉邊，然後想辦法$O(1)$判斷這個點會不會跑到這條線段上就可以了。這裡要用相對運動來看會好做很多。假設現在要判斷的是$A$上的一條線段和$B$上的一個頂點$X$是否會在運動的時候碰到，想像站在$P$點看所有東西，並且面對的方向是跟著$A$一起轉的，也就是當$A$順時針旋轉了$\theta $度之後面對的方向也跟著順時針轉$\theta $度，那麼我們看到的$A$上的這條線段會是永遠不動的。設時間$0$時$Q$的座標為$(a,b)$，$X$的座標為$(x,y)$，那麼可以知道$X$被旋轉了$\theta $度之後他在時間$0$的座標系上的座標會是$M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix}$，其中$M_{\theta}$代表的是可以將一個點以原點為中心逆時針旋轉$\theta $的矩陣。但此時我們的座標系已經順時針旋轉$\theta $度了，所以這時候看到的$X$點的座標必須要逆時針旋轉$\theta $度才是對的，也就是等於$M_{\theta}(M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix})=\begin{bmatrix}x-a\\y-b\end{bmatrix}+M_{\theta}\begin{bmatrix}a\\ b\end{bmatrix}$，由這個式子就可以看出這是一個以$(x-a,y-b)$為圓心，半徑為$\sqrt{a^2+b^2}$的圓了，因此只要寫個線段和圓是否有相交的函式就可以了。
code :
[CF 498E] Stairs and Lines
作法：
首先大概可以想到是從左到右一行一行決定的狀態壓縮DP。考慮把 $dp[i][j]$ 定為：只看左邊數來第$1$條到第$i$條鉛直線，並且在第$i$條鉛直線上的有塗色和沒塗色的狀態壓起來為$j$，此時的方法數。那麼我們就可以先對七種不同的高度預處理出有哪些轉移，也就是先處理好狀態$j_1$轉移到狀態$j_2$有幾種方法，具體來說只要枚舉他們之間的橫線的狀況就好了，如果對於某種橫線的取法是可行的那麼就在這兩個狀態的轉移方法數上加$1$。這樣每行都有最多$2^7=128$種狀態，每個狀態最多也是$128$種轉移，所以如果直接做的話時間會爆掉。而這只要在多注意到我們可以用矩陣乘法來取代轉移過程，因此把DP的過程改成快速冪就可以了。
code :
首先大概可以想到是從左到右一行一行決定的狀態壓縮DP。考慮把 $dp[i][j]$ 定為：只看左邊數來第$1$條到第$i$條鉛直線，並且在第$i$條鉛直線上的有塗色和沒塗色的狀態壓起來為$j$，此時的方法數。那麼我們就可以先對七種不同的高度預處理出有哪些轉移，也就是先處理好狀態$j_1$轉移到狀態$j_2$有幾種方法，具體來說只要枚舉他們之間的橫線的狀況就好了，如果對於某種橫線的取法是可行的那麼就在這兩個狀態的轉移方法數上加$1$。這樣每行都有最多$2^7=128$種狀態，每個狀態最多也是$128$種轉移，所以如果直接做的話時間會爆掉。而這只要在多注意到我們可以用矩陣乘法來取代轉移過程，因此把DP的過程改成快速冪就可以了。
code :
2015年5月21日 星期四
[CF 545E] Paths and Trees
作法：
首先把所有在最短路徑上的邊都找出來，並且定好方向（方向為到源點距離小的連到到源點距離大的），那麼可以知道其實最短路徑樹就是這些邊的一個有向生成樹，並且顯然一棵有向生成樹一定會是最短路徑樹（因為從原點到每個點經過的邊都是最好的邊）。而題目要求的是權值和最小的最短路徑樹，因此就等價於這張圖的最小有向生成樹（MDST）。回顧DMST的作法，第一步是先幫每個非源點的節點選擇權值最小的入邊，如果這些邊沒有形成環就結束了。而很幸運的因為這些都是最短路徑樹上的邊，所以顯然不會形成環，因此直接這樣取就會形成一棵樹了。
code :
首先把所有在最短路徑上的邊都找出來，並且定好方向（方向為到源點距離小的連到到源點距離大的），那麼可以知道其實最短路徑樹就是這些邊的一個有向生成樹，並且顯然一棵有向生成樹一定會是最短路徑樹（因為從原點到每個點經過的邊都是最好的邊）。而題目要求的是權值和最小的最短路徑樹，因此就等價於這張圖的最小有向生成樹（MDST）。回顧DMST的作法，第一步是先幫每個非源點的節點選擇權值最小的入邊，如果這些邊沒有形成環就結束了。而很幸運的因為這些都是最短路徑樹上的邊，所以顯然不會形成環，因此直接這樣取就會形成一棵樹了。
code :
[CF 500G] New Year Running
作法：
這題我的作法是按照官方解的作法寫的，這裡大概提一些官方解裡比較沒有寫到的東西，還有我的實作方法。
首先是求出兩條路徑的共同部份（對了，我的記號是記兩條路徑分別是$u_1$~$v_1$和$u_2$~$v_2$），還有之後需要用到的重要的數字$f_1,f_2,t_1,t_2,t_3,t_4,dis$，其中$f_1,f_2$分別代表兩條路徑的兩倍長，$dis$則代表兩條路徑共同部份的長度，$t_1,t_2,t_3,t_4$則和題解中的定義一樣。這裡先假設在$u_1,v_1,u_2,v_2$中沒有任何一點是另一點的祖先，這種情形的算法可以直接套到一般情形上。至於為什麼我目前也不是很清楚，不過大概可以想成：如果$X$是$Y$的祖先，那麼可以把$X$替換成另一個虛擬節點$Z$，然後把$X$接到$Z$底下，並且在他們之間連一條長度為$0$的邊，這樣不會影響到我們要求的任何東西。有了這件事之後，可以發現給定的這四個點形成的圖形只會有以下兩種：
再來則是轉換後的數論問題，第一部份是要能夠求出以下問題的答案：給定$a,b,c,d\geq 0$，求出在所有滿足$ax+b=cy+d$的整數$(x,y)$中，當$ax+b$為最小的非負值的時候其值是多少。移項變成$ax-cy=d-b$，因此可以直接套用擴展歐幾里得算法求出一組$(x,y)$的解，再把他調整成讓$ax+b$值最小的解。而在調整的時候如果是用慢慢加的會TLE，要算好要加幾倍再一次加上去才可以，看code應該比較好理解。
再來則是第二部份，也就是求$g$函數的值的部份，我覺得他寫的怪怪的所以自己弄了一個作法。這裡我的記號和他不太一樣，$g(a,b,y,M)$會回傳最小的非負整數$x$，使得$a\leq (x\cdot y)\mod M\leq b$，並且$a,b$滿足$0\leq a\leq b<M$。想像$x$從$0$開始慢慢往上加，那麼$x\cdot y$就會一直$+y$，當他加到$\geq a$的時候，如果他的值$\leq b$，那麼顯然此時的$x$就是最小的解了，直接回傳就可以了，也就是第一步是先確認$\geq a$的最小的$y$的倍數是否可行，如果可以的話就直接回傳。如果不行的話，那麼就代表$a$和$b$之間沒有任何$y$的倍數（包含$a,b$），這件事等一下會用到。那麼此時引入另一個變數$r$，把方程式改寫成$a\leq x\cdot y-M\cdot r\leq b$，也就是我們要求滿足上式的二元組$(x,r)$中，$x$的最小值是多少（當然$r$也要$\geq 0$）。而可以看出$r$越小$x$就越小，所以其實也可以先找出$r$的最小值再推出所求的值。再把這條式子反過來變成$-b\leq r\cdot M-x\cdot y\leq -a$，這時候因為$a,b$之間沒有$y$的倍數，所以可以把這條式子直接模$y$，把最左邊和最右邊都變成介於$0$到$y-1$的數字而不會反號（也就是變成$((-b)\% y+y)\% y$）。也就是現在變成了一個新的問題：求最小的$r$使得$A\leq (r\cdot M)\mod y\leq B$，其中$A$和$B$是剛才提到的值。注意到我們可以把$M$改成$M\% y$，也就是變成了$A\leq (r\cdot (M\% y))\mod y\leq B$，因此這樣就可以遞迴下去處理了，他的過程就和輾轉相除法類似，所以複雜度會是$log$級別的。另外還要注意到，如果此時$M\% y = 0$的話遞迴下去可能會有問題，不過不難發現此時一定無解，所以直接回傳就可以了。
另外在使用這個函式之前還會有些問題。回到官方解中我們要解決的那條式子，此時他形如$yf_2+a\leq xf_1\leq yf_2+b$，要求出最小的非負的$x$是多少。如果直接把$a$和$b$拿去模掉$f_2$然後丟$g$函式的話會有問題，因為有可能$a$和$b$之間有$f_1$的倍數，模下去之後就沒了之類的，因此我們先判斷$x=0$或$y=0$的時候這條式子有沒有解，如果有就直接回傳，沒有的話才用$g$函數來算。
對了，出題者在下面的留言說因為他作過了這題（也就是求$g$函數的值的裸題）所以才會的，可以在傳這題之前用來測測看$g$函數有沒有寫對。
code :
2015年5月20日 星期三
[CF 506C] Mr. Kitayuta vs. Bamboos
作法：
這題我是完全照著官方詳解的第二種作法寫的，看了很久一直看不懂第一種作法，這裡就紀錄一下大概怎麼實作的。
在二分搜一個值的時候，一開始所有竹子都同高，只是縮短的速率不一樣。我們可以把所有竹子分成三類，第一類為那些「一直不理他到最後一天高度還是$\geq $他的$h$值」的竹子，我們可以完全不用理他，因為永遠不用把他拉長。至於第二種竹子則是「一直不理他直到最後一天高度會$<$他的$h$值，但不會$<0$」，第三種則是最後一天結束會$<0$的。我們可以先用貪心處理第三種竹子，把他們全部都變第二種之後，剩下的拉長操作的次數就可以依照任意順序對竹子們使用了。貪心的詳細一點來說就是，對每個第三種的竹子都算出「如果一直不理他，那到哪一天他的高度會$<0$」，那麼就只要把他們丟入一個priority_queue中，每次取天恕最小的那跟竹子出來把他拉長，並用一個陣列$num$紀錄每個竹子被拉長了幾次，那麼就可以用$\left \lfloor \frac{h_0+num[i]\cdot p}{a[i]} \right \rfloor+1$算出不理他的話第幾天會$<0$了（其中$h_0$是此次二分搜的值，也是所有竹子的初始高度）。而我的寫法不太一樣，是把第二種和第三種合併處理，也就是一樣都對他們計算上式的值並且丟進priority_queue裡面，只不過所有第二種竹子算出來的值都會$>m$，因為他們在最後一天並不會$<0$，而這也不影響第三種竹子的處理，因為第三種竹子一定會比第二種竹子早出隊，並且保證當 pop 出來的是第二種竹子的時候，所有的第三種竹子都處理完畢了。另外只要再判一下現在被拉長的這個竹子是否已經變成第一種竹子了就好了，如果還沒的話就繼續丟進priority_queue中。當所有程序結束時，priority_queue為空若且唯若此次是成功的。
code :
2015年5月18日 星期一
[CF 504E] Misha and LCP on Tree
作法：
這題我是寫hash的作法，官方解裡有提到用樹鍊剖分 + 後綴數組的作法，雖然他講的沒有很清楚，不過官方解的code寫的很好懂，建議可以參考看看。
首先二分搜答案，只要先求出「這條路徑上的第$t$個點是誰」，就可以把問題轉化成判斷樹上的兩條路徑代表的字串是否相等，因此我們需要求出這兩個字串的hash值，也就是我們需要計算樹上任意一條路徑的hash值。而這可以分成「沿著路競走一路往上」、「沿著路徑走一路往下」、「沿著路徑走先往上再往下」幾種情形，所以對於前兩種情形，我們就必須在每個節點 $i$ 紀錄兩種hash值，兩個hash值都是從 $i$ 走到根所對應的字串的hash值，不過一個是$s[root]+...+s[i]\cdot X^{dep[i]}$，一個是$s[root]\cdot X^{dep[i]}+...+s[i]$，其中 $s$ 為原始字串，$dep[i]$ 為這個點的深度，並且$dep[root]=0$，這兩個值都可以在DFS時順便算好。再來則是如何求出所求的hash值，首先前兩種情況是顯然的，至於第三種情況，我們要先找到兩個點的LCA，在把兩段的hash值合併，而合併的式子稍微推一下就可以了。
但這樣傳上去TLE了，畢竟是$O(Qlog^2n)$的解，官方解也說hash的解太慢了需要優化。首先就是官方解提到的「離線作詢問$k$級祖先」，因為離線處理「詢問節點$x$的$k$級祖先」可以做到$O(n+Q)$，方法也不難，在DFS時維護一個stack就可以了。具體作法是，先把所有詢問讀進來，求出每條路徑兩端點的LCA，並且對每個詢問都紀錄兩個值 $l,r$ ，代表當前這個詢問的解的區間，在每個階段對每個詢問跑一次，如果這個詢問的區間長度已經是$1$了那就略過，至於不是的話，等於是現在我們要詢問長度$mid=\frac{l+r}{2}$是否可行，所以此時可以知道這個詢問會需要知道「誰的幾級祖先是誰」，所以就可以把所有這些東西紀錄下來。跑完所有詢問一次之後DFS一次處理剛才所需要的答案，然後就可以再跑一次所有詢問計算此時的兩個hash值，並且判斷他們兩個是否相等了。
但這樣傳上去還是TLE了，後來我測了一下，發現光預處理每個詢問裡兩點LCA的部份就已經花了$4$秒了，所以我把求LCA的部份也改成離線的作法，離線作LCA可以做到$O((n+Q)\alpha (n))$，詳細作法可以查查LCA的 tarjan 算法。苦苦的改完後竟然還TLE了......最後發現是因為取模太慢了，把 「$ret=(ret\% MOD+MOD)\% MOD$」的外面那層改成用「如果小於 $0$ 就加MOD」就壓線過了，這題的時限太恐怖了OAO
後來我去看別人的作法，這份code跑的速度最快，他的作法是樹鍊剖分套hash，寫的也蠻好懂的，建議也可以參考看看。
code :
2015年5月17日 星期日
[CF 506E] Mr. Kitayuta's Gift
作法：
關於這題的官方解，前面寫的還蠻清楚的，不過後面有跳過一些東西，所以這裡只把後半部的詳細解釋一下。對了，我習慣用$n$代表字串長度，而題目裡的多加字母的個數則用$m$表示。從官方解中的第一張大圖開始（有$O(n^2)$個紅綠節點的那張圖），因為每條鍊是獨立的，所以我們可以分開計算每條鍊上的答案再加起來。而單看一條鍊時，現在上面有一些紅綠交錯的節點，這時可以發現其實他們排列的順序其實不影響答案，只和他是幾個紅點幾個綠點組成的有關，所以可以任意交換位置，才能變成官方解圖中「先全部都是紅再全部都是綠」的鍊。因此這時候我們得到了很多種很類似的鍊，並且我們知道每種鍊的倍率，也就是每種鍊分別有幾條（或是說當我們算完每條鍊的答案之後他們分別要乘以多少，加起來才是答案）。假設第$i$種鍊有$i$個紅點，那麼可以推出此時有$\left \lceil \frac{n-i}{2} \right \rceil$個綠點，如下圖。（這裡舉$n=6$當例子）
最後還有詳解最後一部份的「扣掉違反規則的字串個數」，先回去看第一張官方解的大圖，看那些代表$dp[i][i+1]$的節點們，如果有綠色的節點，那麼就代表從起點走到這個節點的長度為$K-1$的路徑都是不滿足條件的。於是我們可以把「代表$dp[i][i+1]$的綠節點們」當成終點，所以這時候也可以把所有的路徑都拆開，並且一樣用DP求出「有$x$個黑點的路徑」分別有幾條，再作一次上述的步驟就可以了。而這兩次不一樣的地方在於：如果這次有$x$個黑點，那麼白點的個數會是$\left \lceil \frac{n-2-i}{2} \right \rceil$，還有這次從終點到終點的轉移只有$25$種，第一次作的時候是有$26$種的。
code :
訂閱：
文章 (Atom)