退位計劃

全部顏色都選的限制很強，考慮對他容斥。

首先我們可以很容易求出 \(n\) 個點最多用 \(k\) 個點的答案為 \(k(k-1)^{n-1}\)。

那么我們此時多算了某個顏色沒選的答案，需要減掉他，于是答案就顯然了。

\(\sum\limits^{k}_{i=1} -1^{k-i}\times {k \choose i}\times i(i-1)^{n-1}\)

單調棧

考慮一下對于一個 \(b_i\neq-1\) 他會對值有什么限制。

不難發現 \(j \in (b_i+1,i)\) 有 \(a_j\le a_i\) 且 \(a_i<a_{b_i}\)。第一個條件不好搞。

轉化一下第一個條件發現第三個條件是對于每個 \(b_i=-1\) 要找到最小的 \(j\) 滿足 \(j>i\) 且 \(b_j<i\) 需要有 \(a_i\le a_j\)。又由于 \(b_i\neq-1\) 也有這個限制條件，所以當自己不是最小的指向 \(b_i\) 的點，第二個條件改為 \(a_i<a_{las_{b_i}}\)，其中 \(las_{b_i}\) 為上一個 \(b_j=b_i\) 的位置 \(j\)。

現在我們得到了每個點與其他點的大小關系，發現形成森林。那自然設 \(f_{i,j}\) 表示點 \(i\) 選數 \(j\)，直接 DP 就可以了。

樹之間不影響所以最后掃一遍每個樹的根統計一下答案即可。

Two Permutations

顯然我們只關心 \(P\) 的每一位匹配的位置，剩下的就是 \(Q\) 的匹配。而每一位的 \(P\) 是確定的，也就是說每一位在 \(S\) 中只有兩個匹配位置。

這個限制非常強，我們可以對其 DP。

設 \(f_{i,0/1}\) 表示 \(P\) 的第 \(i\) 位匹配 \(S\) 中第 \(1/2\) 次出現的 \(P_i\)，轉移討論一下就可以了。

傳送

還沒寫

B

非常喜聞樂見的想到差分，那么區間取反就是頭尾的 01 取反，區間翻轉就是區間頭和區間尾建邊。

我們把所有操作建邊，最短路就知道把任意兩個 1 變成 0 的答案，這個可以預處理好。

枚舉哪兩個一起變，直接計算最小值。

取模

顯然對 \(2\) 取模就有答案為 \(2\)，只需要看答案是否可以為 \(1\) 即可。

從序列中隨便找三個數，必然有兩個模數相同，枚舉差的因數就可以找到這個模數。剩下的一個數減余數取個 gcd 看下是否有就可以了。時間復雜度是 \(O(n\log V)\)，取極差小的 \(V\) 可以卡過去。

quq

首先有貪心，把 \(a\) 從大到小排序，那么在取完 \(a_i-a_{i-1}\) 之前不會用 \(i-1\) 號扭蛋機。

那么對于一個數 \(i\)，所有大于 \(i\) 的已經扭到了，但是 \(i\) 沒有扭到，這個概率為 \(\frac{1}{n-i+1}\)，考慮選到 \(<i\) 對兩者都無影響，也就對概率無影響，否則就會在這其中選一個。每次都不選到 \(i\) 且后面全部選完的概率就是 \(\frac{1}{n-i+1}\)。

在這個概率下，我需要選出這個。扭包含這個值的最小的扭蛋機，出他的期望次數就是值域。這個感性理解即可。

最后的答案把這些乘起來相加即可。

求排列(roast)

拆位。

找到最高的一位，這一位既有 \(0\) 也有 \(1\)，那么必然有不同數的跨度。也就是說答案的這位必然是 \(1\)。

那么把數按照這一位分成兩個集合，集合內亂走是不會影響答案的，只有跨集合會影響答案。

則一個集合建字典序，一個集合查異或最小值，集合之間的邊左右兩邊異或必然是這個最小值，否則走這個邊就是不優的。

接下來就變成走路題了，需要保證任意時刻不走到割點。一個點是割點只能是所有去對面的邊都掛在這個節點上了。

所以按照字典序貪心，先找合法起點，他要么不是割點，要么就是集合內唯一的點。向前走一步，如果集合還有點，就不能走割點，其他就在出邊中找最小值。

走完一圈就得到答案了。

仙人

無腦圓方樹。

變成樹后對于每個子樹進行DP。

對于 \(u\)，我們考慮一個子樹 \(v\) 合并進來的貢獻。拓撲序減去自己在最前面長 \(siz_u-1\)，合并長為 \(siz_v\) 的拓撲序，由于子樹之間是互不影響的，所以可以任意取位置，取完后要把這些位置刪掉，則有 DP：

不過注意方點是沒有 \(siz\) 貢獻的，而且最遠點是要強制在最后的，所以剛才的 DP 不能用。

重設個 \(n^2\) 的 DP \(g_{l,r}\) 表示第 \(l\) 到 \(r\) 兒子排拓撲序的答案，則有

均攤時間復雜度 \(O(n^2)\)。

[5102IOSJ]最大公約數

福利題。

因為 \(n=1000\)，所以 \(n^2=10^6\)，但是 \(n^4=10^12\)，所以考慮 \(n^4\) 來做這個題。

枚舉矩陣左下 \((i,j)\) 和右上角 \((f,k)\)，不難發現 \(gcd(i,j,f,k)=\operatorname{gcd}(gcd(i,j,f,k-1),\operatorname{gcd}(gcd(i,j,f-1,k),a(f,k)))\)。現在我們獲得了一個 \(n^4\) 的做法。考慮優化它。

先優化空間，我們發現可以去掉前兩維，這樣可以跑 \(1000\) 的數據。

然后我們發現，若 \(gcd(f,k)=1\)，那么對于任意 \(f'>f,k'>k\)，有 \(gcd(f',k')=1\)。可以剪枝優化。

分析時間復雜度。當數據是隨機的，一但我們找到任意一個數與當前集合內任意數互質，那么我們就會退出。發現這樣集合大小期望不會很大，大概 \(100\) 左右，所以時間復雜度期望 \(O(100n^2)\)。