#11 ARC104D

題目傳送門

首先，看到平均值套路地做轉化：給每一個數減去 \(x\)，然后求和。

轉化后序列變成兩段，每一段的值域都形如 \([1,r]\)。

那么我們考慮 dp 計數，定義 \(f_{i,j}\) 為考慮了小于等于 \(i\) 的數，且此時為 \(j\)。

轉移是 naive 的，答案就是 \((k+1)\sum \limits_{i=1}^n\sum \limits_{j=1}^{n(n-1)/2}f_{i-1,j} \times f_{n-i,j}\)。

但是直接做是 \(O(n^3k^2)\) 的，非常不可過。

于是我們考慮前綴和優化多重背包。具體地，我們先當完全背包做一遍，然后我們考慮對 \(f_{i,j}\)來說，第 \(i\) 維上的有效貢獻區間為 \([j,j-ki]\)，于是我們減去 \(f_{i,j-i(k+1)}\) 即可。

值得一提的是，這個優化方法能且僅能用于多個轉移貢獻可加的背包，不能處理多個轉移取 \(\max\) 的背包。

時間復雜度為 \(O(n^3k)\)，常數極小，時限充裕。

#12 ARC107D

題目傳送門

巧妙轉化！

我們考慮將集合內的元素按升序安排，例如 \(\{\frac{1}{16},\frac{1}{8},\frac{1}{2},\frac{1}{2}\}\)。那么我們可以把其視為由 \(\{1,1,1,1\}\)，在 \([1,1]\) 乘一個 \(2^{-1}\)，在 \([1,2]\) 乘兩個 \(2^{-1}\)，在 \([1,3]\) 乘一個 \(2^{-1}\) 得到。也是說我們可以通過在若干個前綴上乘若干個 \(2^{-1}\) 得到。然后據此 dp 即可。

值得注意的是，因為結果是整數，所以我們在 dp 過程中可以忽略出現小數的情況。

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

#13 ARC197D

題目傳送門

首先，我們要明確一件事：對于一對父子，與兒子在同一條鏈上的點不多于與父親在同一條鏈上的點。（因為父親可能有其他子樹，這些子樹內的點和該兒子不在同一條鏈上）。

因此，如果兩個點 \((u,v)\) 有邊，那么必然存在 \(a_u \cup a_v=a_u\) 或 \(a_v \cap a_u =a_v\)，且深度關系確定。

那么我們考慮 \(a_u=a_v\) 的情況，這時候這兩個人誰當父親都行，也就是說可以任意排列它們在鏈上的順序。因此對于一個大小為 \(sz\) 的 \(a\) 相同的極大團，它對答案有 \(sz!\) 的貢獻。

小細節：\(1\) 是所有人的祖先。

#14 P8136

題目傳送門

首先，我們可以把任務分為“好任務”（可以獲得倍增器的任務）和“普通任務”（不能獲得倍增器的任務）。

那么我們觀察到：一定存在一個任務順序，使得我們先做好任務，再做普通任務。

證明：如果存在一個兩個任務 \(i,j\)，且 \(i\) 是普通任務，\(j\) 是好任務，且 \(i\) 先于 \(j\) 做,我們設當前經驗為 \(xp\)。那么有 \(xp \ge vd_i,xp+x_i\le vd_j-1\)；如果我們交換 \(i\) 和 \(j\) 的順序，那么有 \(xp \le vd_j-1，xp+cx_j\ge vd_i\)。兩個任務性質不變，因此交換不會變劣。

其次，我們再觀察到：普通任務的順序不影響最后經驗值。

因為順序只關系我們能否獲得增幅器，既然已經不能獲得增幅器了，那么順序也就沒有意義了。

最后，我們有一個驚人注意力：我們定義 \(mx_i=vd_i+cx_i-1\)，即做完任務 \(i\) 時可能的最大經驗值，那么我們會優先做 \(mx_i\) 小的好任務。

證明：

我們假設存在兩個好任務 \(i,j\)，\(i\) 先于 \(j\) 做且 \(mx_i>mx_j\)，那么可以推斷：

那么我們要判斷 \(xp+cx_j\) 和 \(vd_j-1\) 的大小關系，注意到：

因此交換 \(i\) 和 \(j\) 的順序不會改變任務的性質，不會使答案變劣。

根據上述性質，我們按照 \(mx_i\) 給任務升序排序，那么依照這個順序 dp 即可。

這個 dp 類似于背包，我們定義 \(f_{i,j}\) 為考慮到第 \(i\) 個物品，是否可以使從任務獲得的經驗為 \(j\)。轉移時欽定當前物品是否在好物品集合中，這是簡單的。找答案就倒序枚舉 dp 數組，找到一個可以的經驗值。

我們定義 \(m=nc \times\sum x_i\)時間復雜度為 \(O(nm+n\log n)\)，接近 \(1.6 \times 10^{13}\)，非常不可過。

考慮優化：

• 我們可以把好任務獲得的經驗分成 \(x_i\) 和 \((c-1)x_i\)，這樣我們就可以只統計后面那部分的貢獻。換句話說，我們可以只關心好任務的選取情況；
• 因為所有好任務提供的經驗的都有 \(c-1\) 的系數，將其提出，可以降低值域大小；
• \(01\) 背包可以使用 bitset 優化；

經過上述優化后，我們定義 \(m=n\times \sum x_i\)，時間復雜度為 \(O(\dfrac{nm+m \log m}{w})\)。

#15 CF587F

題目傳送門

先考慮答案怎么求。因為包含一個字符串的串，在 fail 樹上體現為這個串的結束節點及其子樹。所以我們可以每一個字符串的結束節點及其子樹加一，然后對字符串的每一個節點進行一次單點詢問，權值和就是出現次數。

那么我們有兩種答案統計方式：“統計”和“被統計”。

首先，我們考慮自己統計答案。我們把詢問離線，然后類似掃描線地拆詢問，然后每掃到一個串，就把它結束節點及其子樹加一，然后做詢問時直接枚舉節點做單點詢問，時間復雜度為 \(O(|s|\log m)\)。

然后，我們考慮讓別人幫我統計。我們先把字符串上每一個點加一，然后枚舉區間內的字符串，詢問其結束節點及其子樹的權值和，時間復雜度為 \(O(m\log m)\)。

那么我們考慮平衡復雜度，我們定義一個閘值 \(T\)：

• 若 \(s_i \le T\)，我們用第一個方式統計答案，時間復雜度為 \(O(n\log m+qT \log m)\)，使用分塊可以做到 \(O(n\sqrt m+qT)\)。

• 若 \(s_i>T\)，我們用第二個方式統計答案，時間復雜度為 \(O(\dfrac{m^2}{T}+q \log m)\)。

那么時間復雜度為 \(O(\dfrac{m^2}{T}+qT\log m+q\log q+n\log m)\)，當 \(T=\dfrac{m}{\sqrt{q\log m}}\) 時取到最優時間復雜度為 \(O(n \log m+q \log q+m \sqrt{q\log m})\)。

#16 CF1110H

題目傳送門

狀態壓縮好題。

我們先考慮如果確定一個大數，我們怎么統計答案。我們可以把 \([l,r]\) 內的每一個數都加入 ACAM，然后進行多模式串匹配。

如果 \(r-l+1\) 比較小呢？我們可以在 ACAM 上跑 dp。我們定義 \(f_{i,j}\) 表示長度為 \(i\) 且在 \(j\) 狀態的最大權值，\(g_i\) 表示 \(i\) 狀態的權值，那么有 \(f_{i,u} =\max \limits_{c,v=tr_{u,c}} f_{i-1,v}+g_u\)。\(g\) 數組的預處理是 \(fail_u\) 向 \(u\) 貢獻。

但是本題 \(r-l+1\) 非常大，說明 ACAM 上節點非常多，我們沒有辦法樸素 dp。但是這是一個數位上的 ACAM，且插入的數連續，那么 Trie 上會有非常多的相同結構（也就是滿十叉樹），那么我們觀察對于一個滿十叉樹，它無論怎么走貢獻是確定的（只有葉子節點的貢獻（因為只有這一個結束節點），也就是 \(1\)），這啟發我們對這樣的子樹直接預處理它的貢獻，然后直接砍掉。

具體地，我們考慮擴展 \(g\)。我們定義 \(g_{i,j}\) 表示在 \(i\) 狀態后加 \(j\) 個字符可以獲得的權值。因為 \(g\) 數組內的貢獻是額外的，和 fail 樹上祖先貢獻是無關的（因為這里的貢獻是子樹內葉子節點的貢獻，我們都沒有建出這個節點，更不要說 fail 樹上祖先對它的貢獻了），所以我們可以提前加上。那么轉移就變成：

顯然你可以對 \(g\) 做一個前綴和實現 \(O(1)\) 轉移，然后我們就可以考慮怎么預處理 \(g\) 數組了。

在 fail 樹上的貢獻是一樣的，不再贅述；在開始時，我們考慮類似數位 dp 一樣進行統計，看當前狀態是否卡到上下界，如果都沒有卡，那么就是滿十叉樹，可以直接記錄貢獻。

然后就一些小細節：

• 如果 \(l\) 和 \(r\) 的位數不同：我們就給 \(l\) 補零，然后強制 ACAM 的根節點不允許建 \(0\) 的出邊。
• 找字典序最小的方案：我們考慮從后往前找答案狀態的前驅，然后從前往后輸出方案時優先走最小的字符即可。

#17 CF1988F

題目傳送門

傳奇計數題，充分展現了預處理的魅力。

因為求的是 \([1,n]\) 的答案，所以我們考慮能不能從 \(n-1\) 的答案推出 \(n\) 的答案。

因為前綴最大值個數和后綴最大值個數互不干擾，所以我們可以分開計數。我們定義 \(f_{n,i,j}\) 表示已經插入了 \([1,n]\)，且排列中有 \(i\) 個前綴最大值和 \(j\) 個上升點的方案數；類似地，我們定義 \(g_{n,i,j}\) 表示已經插入了 \([1,n]\)，且排列里有 \(i\) 個后綴最大值和 \(j\) 個上升點的方案。

由對稱可以得到：\(g_{n,i,j}=f_{n,i,n-j-1}\)。因此我們只需要計算出 \(f\) 即可。

我們注意到題目中的定義都之和數的相對大小有關，因此我們可以這么考慮從 \(n-1\) 到 \(n\)：我們將所有數加一后，插入一個 \(1\)。因為插入的是 \(1\)，所以我們一定不會對原有的前綴最大值產生影響。此時我們來大力分類討論一下：

• 把 \(1\) 放在一個上升點后或最后：那么此時我們拆開了一個上升點又產生一個新上升點（你可以理解為 \(1\) 替換掉了原上升點），也就是上升點數不變；如果放在最后，那么顯然上升點個數不變。即 \(f_{n,i,j} \leftarrow f_{n-1,i,j} \times (j+1)\)。

• 把 \(1\) 放在第一個位置：那么此時 \(1\) 既是一個前綴最大值，又是一個上升點，即 \(f_{n,i+1,j+1} \leftarrow f_{n-1,i,j}\)。

• 把 \(1\) 放在其他位置：那么此時 \(1\) 會使后面的點變成上升點，即 \(f_{n,i,j+1} \leftarrow f_{n-1,i,j} \times(n-j-2 )\)。

那么直接做空間復雜度為 \(O(n^3)\)，但是我們注意到 \(i\) 轉移時只需要 \(i-1\) 的值，因此可以滾動數組優化。

那么我們接下來考慮統計答案：

因為 \(n\) 是數列中最大的數，因此它既是前綴最大值又是后綴最大值，且其他前綴（后綴）最大值一定出現在 \(n\) 之前（之后），所以我們可以以 \(n\) 為界，把數組分為左右兩部分。然后我們枚舉其中一邊的情況，然后就有：

\(O(n^6)\) 非常不可做，我們考慮降維。

我們注意到：\(f_{p-1,i,x}\) 和 \(a_{i+1}\) 只有三個不同的變量，也就是說我們可以在 \(O(n^3)\) 內把它們的積預處理出來，所以我們令 \(u_{i,x}=\sum \limits_{p=1}^if_{p-1,i,x}a_{i+1}\)；類似地，我們記 \(v_{j,y}=\sum \limits_{p=1}^{i}g_{n-p,j,y}b_{j+1}\)。

然后我們成功將原式簡化為：

再觀察，我們注意到 \(u_{p-1,x}\) 和 \(c_{x+y+[p>1]}\) 只有三個不同變量，于是我們記 \(w_{p,y}=\sum \limits_{x=0}^{p}u_{p,x}c_{x+y+[p>0]}\)（這里看似變化很大，其實也只是把 \(p-1\) 換成了 \(p\) 而已）。

于是我們就有一個最終的式子

#18 AGC027E

題目傳送門

首先，這類變化很大的題目一般有某種比較強的不變量限制。

我們觀察后發現：我們把 a 看成 \(1\)，把 b 看成 \(2\)，那么我們變換前后得到的字符串的權值 \(\bmod 3\) 的結果不變。

我們再觀察可以發現：如果原串中存在一對相鄰的相同字符，那么我們一定可以通過變化使得該串最后變為一個字符。

那么我們就把問題轉化為：把原串劃分為若干個子串，然后把每一段轉化為一個字符，詢問有多少中本質不同的字符串。

值得注意的是，我們在劃分時并不要求子串內有相鄰字符，因為如果該子串無法操作，那么我們可以把該子串和下一個子串合并，然后變成將該子串劃分為兩個合法子串的子問題，這個問題遞歸處理下去，最后一定存在合法的劃分方式。

接下來就可以進行 dp 了。我們定義 \(f_i\) 表示原串上 \([1,n]\) 的劃分方案數，\(a_i\) 為 \([1,i]\) 的字符串權值和。然后為了使本次劃分的子串可以轉化為一個字符，所以我們要從 \(a_i \neq a_j\) 的 \(j\) 轉移過來；同時，為了保證我們不重復統計字符，我們欽定從上一個 \(a_j\) 轉移過來。同時，如果 \([1,i]\) 可以轉化為一個字符，那么我們可以直接操作，因為這樣得到的字符串長度為 \(1\)，從其他位置轉移過來得到的字符串長度至少為 \(2\)，可以保證不會重復計算。

#19 CF1305G

題目傳送門

首先，我們考慮刻畫操作 \(2\)。因為每一個點只能加入一次，且加入一個點后會給所有和它有連邊的點染色。因此我們考慮是否可以通過生成樹來刻畫操作。

考慮一條邊 \((u,v)\)，如果它被加入，那么它的貢獻可能是 \(a_u\) 也可能是 \(a_v\)，這取決于加入該邊時加入的是誰。

一個 Trick 是：我們把邊權定義為 \(a_u+a_v\)，然后答案就是所有在生成樹上的邊的邊權之和減去所有點權之和；特別地，我們開一個權值為 \(0\) 的虛點，然后向每一個點連邊。

接下來貪心地從大到小枚舉邊權，然后枚舉邊的兩邊分別是誰，時間復雜度為 \(O(3^{18}\alpha(n))\)。

#20 P11292

題目傳送門

傳奇 dp 題。

我們首先考慮 \(cnt_i^2\) 的組合意義：就是選出兩條顏色為 \(i\) 的同色鏈的方案數。

那么我們只需要欽定兩條鏈同色，那么其他點的顏色就無所謂了。

因此我們考慮這個時候對答案的貢獻系數，我們假設在兩條鏈上有 \(c\) 個點重合，那么系數為 \(2^{n-2l+c+1}\)。

考慮只有 \(c\) 是變量，將其分離：也就是將系數分為 \(2^c\) 和 \(2^{n-2l+1}\) 兩部分。

那么我們只需要統計重合點為 \(c\) 的方案數即可。

直接統計恰好有 \(c\) 的重合點的方案數不太簡單，我們考慮進行二項式反演，轉化為欽定 \(c\) 個重合點的方案數。

自然地，我們想到 dp。我們定義 \(f_{u,c,l1,l2}\) 為在 \(u\) 點，已經欽定 \(c\) 個點，一條鏈長度為 \(l1\)，另一條鏈長度為 \(l2\) 的方案數。

轉移的時候我們枚舉一個點 \(v\)，然后轉移到 \(f_{v,c+1,l1+t1,l2+t2}\)，系數為 \(to_{u,v,t1}\times to_{u,v,t2}\)，其中 \(to_{u,v,k}\) 表示從 \(u\) 到 \(v\) 經過 \(k\) 條邊的方案數。為了定義初始狀態 \(f_{u,1,l1,l2}\)，我們要預處理 \(st_{u,l}\) 表示經過 \(l\) 條邊到 \(u\) 號點的方案數；為了統計答案，我們要預處理 \(ed_{u,l}\) 表示從 \(u\) 經過 \(l\) 條邊的方案數。

然后預處理 \(to\) 是 \(O(n^3l)\) 的，\(st,ed\) 的預處理通過 \(to\) 得到，時間復雜度是 \(O(n^2l)\)。

dp 轉移是 \(O(n^2l^5)\) 的。

我們考慮優化 dp 過程。注意到 \(t1,t2\) 的轉移是獨立的，考慮分步進行。具體地，第一步先轉移到 \(g_{u,c,l1+t1,l2}\)，然后再轉移到 \(f_{v,c+1,l1+t1,l2+t2}\)，時間復雜度降到 \(O(n^2l^4)\)。

dp 過程再優化不太現實，我們考慮從二項式反演入手。具體地，如果我們可以把 \(k^c\) 的貢獻體現到 dp 里，我們就不需要維護 \(c\) 了。

接下是推式子，我們考慮定義 \(f(i)\) 為欽定 \(i\) 個的方案數， \(f'(i)\) 為恰好 \(i\) 個的方案數：

因此，我們只需要在每一次轉移時乘入 \(k-1\) 的系數即可。