P9743 「KDOI-06-J」旅行

先寫出來一個 \(O(n^7)\) 計數方程

復雜度過高，考慮容斥，首先不要被 \(x,y\) 所迷惑，它們是定值，而變量為 \(ca,cb\) 發現連續區間可以進行二維前綴和。寫不下了，第一個式子略去了下標\((x,y)\)

還是有點小細節的，比如 \(c\) 的變化。其實就是讓變量 \(la,lb\) 發生一個偏移 "\(1\)" 同時不要忘記讓其他維度也發生相應變化

P8502 「CGOI-2」No cost too great

顯然以經過的邊數為階段。

設出 \(f_{i,j,k}\) 表示從 \(j\) 到 \(k\) 經過 \(i\) 條邊的方案數，列出方程

如何快速求和？觀察到一個點 \(l\) 所到達的點序號為一個區間，故可用刷表法進行更新，并用差分代替樹狀數組，以此去掉一個 \(\log\) 的復雜度。

至于約束條件可以運用正難則反，去掉經過 \(c\) 的情況。

注意 \(f_{i,j,k}\) 并不代表只經過一次 \(j\)，因為可能從 \(j\) 出發又回到 \(j\) 再去 \(k\)。如果去掉經過 \(c\) 的情況用 \(f\) 減去 \(f\) 相乘求和這樣子算的話肯定會有重復。一般解決辦法是選取一個基準點，這里選擇最后一次經過 \(c\) 的狀態為基準點，只要最后一次經過 \(c\) 的時候狀態不一樣那么總的狀態就不一樣，這樣就不會減去重復的了。此時做法都是再開一個輔助數組，設 \(g_{i,j,k}\) 約束其為最后一次經過 \(j\) 的方案數，而且一般這種輔助數組的遞推要用到原數組，本題中即為在 \(f\) 的基礎上將 \(g_{i,j,j}\) 設置為 \(0\) 即可。

于是在計算 \(f\) 數組的基礎上修改一次即可，得到

ARC144D AND OR Equation

看到題目奇怪的二進制式子，第一眼似乎要用二進制運算找規律？其實不用，可以思考式子的實際意義，即為 $ A_{i}+A_{j}-A_{i \cap j}=A_{i \cup j}$。這樣就是一個集合合并的式子啦。

我們可以構造 \(p_{0 \sim i-1}\)，令 \(A_S =\sum\limits_{i \in S}p_i\)，考慮還有哪些式子符合給出一個偏移量則 \(a'_S=a_S+c\)。

此時可以開始計數，利用題目約束條件可得，\(\sum\limits_{p_i>0} p_i+c \le k\) 并且 \(\sum\limits_{p_i<0}p_i+c \ge 0\)。一個很顯然的想法就是枚舉 \(c\) 然后統計方案。但是我們會發現枚舉完 \(c\) 之后是一個求和式子小于一個數不太好處理，需要枚舉一個可能值再計算這樣就麻煩了。那么我們可以轉換一下思路，直接枚舉求和式，然后 \(c\) 單變量的方案數就很顯然了。

于是直接枚舉正數之和，負數之和以及為 \(0\) 的情況，列出 \(c\) 的范圍是 $ [ -\sum\limits_{p_i<0}p_i,k-\sum\limits_{p_i>0}p_i]$。發現區間長度正好就是 \(k+1-\sum\limits \lvert p_i \rvert\)，這樣又可以簡化了,我們只需要枚舉絕對值之和，不需要分開枚舉了！

答案就是

線性求解即可。

P9753 [CSP-S 2023] 消消樂

哈希

對于每個左端點放一個棧匹配，可以做到 \(O(n^2)\) ，部分分的串是隨機的，我們可以發現隨機情況下合法串應該很短，對每個左端點起掃很少一段距離就行了。

還是減少重復計算的思想，于是直接從頭建立一個棧一直掃到尾部，然后可以發現這題滿足可減性即 \([l,r]=[1,r]-[1,l-1]\)。哈希維護相同的前綴棧就行了。

DP

計數可以往 \(\rm dp\) 方向想，\(dp_i\) 表示以 \(i\) 結尾的方案數，顯然 $dp_i = dp_{j-1}+1 \(。\)j$ 是 \(i\) 的上一個匹配點，此時還是 \(O(n^2)\)，因為瓶頸在于如何快速找到上一個匹配點 \(j\)，也就是找到最大的 \(j\) 為滿足 \([j,i]\) 為合法串。

這和 KMP 很像，也可以利用類似的思路遞推 \(\rm Next\) 數組就行了。

我們來分析一下復雜度，對于一種字母最多跳到某一位置一次，假設 \(i<j\)，\(s_i=s_j\)，如果 \(i\) 的時候枚舉到了那個位置，\(j\) 的時候如果還可以枚舉到那個位置的話顯然就與 \(Next\) 數組定義中的最近相矛盾，因為此時 \([i,j]\) 已經可以構成一個合法區間，故復雜度為 \(O(n \lvert \sum \rvert)\)。

發現構成串的字符種類很少，可以空間換時間。做到空間 \(O(n \lvert S \rvert)\)，但是時間線性。每個位置新增一個字符所以只需要一次修改，記錄一次快速匹配，具體操作可以見題解。

UVA580 危險的組合 Critical Mass

常見解決方法就是利用數學組合數推出一個具體的式子。但是這條路走不通，可以考慮列出遞推公式然后求解。

設 \(f_i\) 為前 \(i\) 個盒子滿足方案，然后很顯然的就是要分類討論 前 \(i-1\) 個盒子滿足了，或者到了第 \(i\) 個才剛剛滿足。前者為 \(2f_{i-1}\) ，后者需要前 \(i-4\) 個不滿足，正難則反一下就是 \(2^{i-4}-f_{i-4}\)。

P3978 [TJOI2015] 概率論

很常規的想法，就是通過 \(i-1\) 的來新增一個節點推導 \(i\) 的答案，看放在哪里可以產生貢獻，發現只有在葉子節點才會產生貢獻。如果不會算可以打表猜規律。

我的想法是從樹中提取出一個單點如果它沒有兒子那么可以左右掛兩個，如果它有一個兒子，可以掛一個，通過另一邊必定會多出一個葉子節點，葉子節點一個點可以掛兩個，如果它有兩個兒子同理，可得 \(n-1\) 的二叉樹可以掛 \(n\) 個葉子節點。

設 \(f_i\) 為 \(i\) 個節點的二叉樹個數，\(g_i\) 為所有 \(i\) 個節點的二叉樹的節點總數。可得 \(g_n=n \times f_{n-1}\) 。問題在于計算 \(f\) , 利用計數思想找到一個基準點，只需要兩個數的左子樹不同那么這個樹就不同，于是有 \(f_i=\sum\limits_{i=1}^{n-1}f_i \times f_{n-i-1}\) ，注意這個遞推式，此時的 \(f\) 為卡特蘭數列，或者你可以通過看前幾項 \(1\) \(2\) \(5\) \(14\) \(42\) 猜出來。利用通項公式求解即可， \(Cat_n= \frac{C_{2n}^n}{n+1}\)。

ABC158F Removing Robots

先找計數基準點，顯然為左邊第一個激活的機器人。設 \(f_i\) 為必須激活左邊的第 \(i\) 個機器人的方案數，則有

記 \(g_i=\sum\limits_{j=i}^{n+1}f_j\)，則有 \(f_i=g_j\)。答案即為 \(g_1\)。

現在來解決 \(k(i)\) 如何求，\(k(i)\) 表示 \(i\) 右邊第一個不受影響的機器人。大概是這么一個過程：在機器人 \(i\) 的覆蓋范圍內找到一個覆蓋范圍最廣的點 \(z\)。由于該點的覆蓋范圍此前已經求出，于是 \(k(z) \to k(i)\)。

這個過程可以通過線段樹完成，但是我們也可以發現本質是維護一系列隨著位置單調遞增，覆蓋范圍也單調遞增的點。于是單調棧就可以了。

ARC074E RGB Sequence

這一種有約束的 \(dp\) 計數題目，設計的狀態里面必須有約束條件。

比如這題是要求區間顏色種數，發現顏色數很少，于是直接設 \(f_{i,j,k}\) 表示上一個與 \(a_i\) 不同的是 \(a_j\), 再上一個與 \(a_i\) 和 \(a_j\) 不同的是 \(a_k\)。這樣就可以快速判斷區間顏色種數。

CF1332F Independent Set

如果枚舉每一個子圖計算的話，必然會重復計算信息，導致復雜度增大。

假設 \(G' \subset G\)，我們可以發現對于 \(G'\) 的計算和 \(G\) 中 \(G'\) 的計算除了子圖 \(G'\) 的根節點外其余都相同。于是我們設出狀態 \(f_{i,0/1/2}\) 分別表示 \(i\) 作為子圖根節點的時候的答案，與父節點聯通時 \(i\) 點的不選或者選。于是有

注意藍筆部分，因為題目中子圖是通過邊集定義的，而題目要求邊集不為空，所以子圖就不能由一個點構成。

AGC008F Black Radius

本題的計數方式并不是以具體的點集來計數，而是基于 \((u,d)\) 的計數，可是可能會有重復。于是我們希望對于任意一個點集 \(T\) 用最小的 \(d\) 來刻畫。顯然除了全集之外，任意一個集合都可以通過最小的 \(d\) 來唯一確定中心點 \(u\)。（先不考慮全集，最后加上即可）。

首先思考給出集合 \(S\) 為全集的時候，對于一個點 \(u\) 如何才能產生貢獻。設 \(f_u\) 表示 \(u\) 的最深子樹的深度，\(g_u\) 為 \(u\) 的次深子樹的深度。首先 \(d \le f_u-1\)，其次為了防止 \(u\) 周圍的點 \(v\) 用 \(d-1\) 的深度覆蓋了 \(u\) 的深度 \(d\)（此時 \(v\) 在 \(u\) 的最深子樹中，且其他子樹的深度被完全覆蓋）。那么需要滿足 \(d \le g_u+1\)，于是 \(S\) 為全集的時候，\(d\) 需要滿足 \(d \in [0,\min(f_u-1,g_u+1)]\)。

考慮如何擴展到子集，為了和之前的形式統一，我們依然可以將貢獻產生放在 \(d\) 最小的點上，哪怕他不是關鍵點。于是有，對于關鍵點 \(d\) 要求同上，對于非關鍵點至少要覆蓋到一個關鍵點，于是 \(d\) 的下界是深度最低的關鍵點子樹深度 \(h(u)\)。

CF1943D2 Counting Is Fun

首先一個小結論，一個序列可以通過長度大于 \(1\) 的區間減變成全 \(0\)，當且僅當對于任意位置 \(a_{i+1}+a_{i-1}\ge a_i\)。

于是我們可以設 \(dp_{i,j,t}\) 表示第 \(i\) 個位置是 \(j\)，前一個位置是 \(t\) 的時候的方案數。

于是我們可以 \(dp_{i,j,t} \to dp_{i+1,z,j}\)，這個時候是 \(O(n^3)\)。
注意一下這種 \(dp\) 的形式，一般這種有狀態重疊的 dp（沒有變化的 \(j\) ），我們可以考慮直接去掉一個維度。
設 \(dp_{i,j}\) 表示第 \(i\) 個位置為 \(j\) 的總方案數。那么下面解決的就是如何消除去掉的那個維度的影響。
首先是 \(dp_{i+1,t} \gets \sum\limits_{j=0}^k dp_{i,j}\)，后面可以用到容斥。

也就是減去該位置不合法的方案數，就是每個 \(dp_{i,j}\) 對應的使得該狀態不合法的 \(dp_{i-1,s}\)，這里注意我們的對象使得 \((i,j)\) 不合法，于是只能是 \(s+t<j\)，而不能是 \(j+t<s\) 這種情況。同時還有一個性質就是不可能出現相鄰兩個位置不合法，這也就為我們使用 \(dp_{i-1,s}\) 提供了保障。

我們不可能對于每個 \((i,j)\) 都累加 \((i-1,s)\) 然后求和，這樣復雜度太高了，于是直接統計每個 \((i-1,s)\) 會出現幾次直接減去 \(dp\) 值乘以對應個數即可。
于是 \(dp_{i,t}=\sum\limits_{j=0}^k dp_{i,j}-\sum\limits_{s=0}^k dp_{i-1,s} \times\max(0,k-t-s)\)

ABC134F Permutation Oddness

看似需要用一個 \(S\) 表示目前用了哪些，十分不可做。

實際上這種問題的狀態只需要和題目中要求的量有關即可，或者說只要當前的狀態可計算答案就行了，狀態里面維護那些產生能貢獻的量即可。

考慮貢獻法，此時每個位置可以拆成兩個 \(i\) 和 \(p_i\)，兩部分都可以產生貢獻。將排列看成 \(\{1,2\dots n\}\) 匹配 \(\{1,2\dots n\}\)，然后決定當前 \(i\) 去匹配 \(<i,=i,>1\)，由此費用提前計算就行了。

我們設 \(f_{i,j,k}\) 表示前 \(i\) 個位置里未匹配的位置有 \(j\) 個，目前總和為 \(k\) 的方案數，這里注意一個小細節很重要就是未匹配的 \(i\) 和 \(p_i\) 數量應該相同，所以我們可以這么設置狀態以減少維度。

向自己匹配：

與后面數匹配：

與前面的數匹配：

一前一后：

一般圖邊覆蓋計數

求 \(S\subset E\) 的個數，滿足 \(S\) 是原圖的一個邊覆蓋。\(n\le 40,m\le 60\)。

參考了本篇博客。

Meet-In-Middle

考慮將圖分為兩部分，每個部分內部設 \(f(S)\) 表示對于 \(S\) 內的點做邊覆蓋的方案數。容易通過狀壓 dp 實現。然后我們只需要枚舉兩個部分之間的跨越邊邊，這些跨越邊會在兩邊分別覆蓋一些點，對于未覆蓋點用 \(f(S)\) 解決，然后對于單個點集內的跨越邊和非跨越邊直接 \(2\) 的次冪累加方案數即可。

復雜度與跨越兩個集合之間的邊的個數掛鉤，所以圖的兩個部分可以進行隨機，取計算量最少的進行統計。

容斥

首先 \(O(2^nm)\) 的做法是顯然的，欽定若干點沒有被覆蓋即可。

還是考慮 meet-in-middle，內部容斥，枚舉兩邊欽定情況，枚舉中間的邊算貢獻，樸素做的時間復雜度還是 \(O(2^nm)\)。但是你枚舉兩邊的欽定情況再枚舉中間的邊算貢獻的時候，可以發現我們只關心在兩個部分之間有邊的點是否被欽定，設個數分別為 \(c_1\) 和 \(c_2\)，可以做到 \(O((2^{\frac{n}{2}}+2^{c_1+c_2})m)\)。

ABC252G Pre-Order

先序遍歷就是 dfs 序，dfs序的子樹就是一段區間，所以我們考慮區間 dp。設 \(dp_{i,j}\) 表示 \([i,j]\) 這一段的方案數。很套路的就得到類似于 \(dp_{l,k} \times dp_{k+1,r} \to dp_{l,r}\) 這樣子的方程，但是注意一下在計數 dp 里面一定要小心要不重不漏，也就說上述區間劃分會造成多統計的，比如區間 \([1,2]\)，\([3,4]\) 和 \([5,6]\) 可以通過 \(dp_{1,4} \times dp_{5,6}\) 產生，也可以通過 \(dp_{1,2} \times dp_{3,6}\) 產生。

解決方法就是欽定第一個劃分出來的區間不同即可，于是我們就要求劃分出來的左區間單獨形成一個子樹，不能再被劃分為多個子樹。這里不需要再開輔助數組 \(f\) 來單獨計數。可以直接通過欽定區間最左邊的一個數為根解決，這樣子當 \([l,r]\) 進行劃分的時候最先劃出來的就是 \([l+1,k]\) 其中由于 \(l+1\) 為根，所以第一個劃分出來的區間只有一個子樹，而為了讓后面劃分出來的右區間可以有形成多個區間的選擇，我們這里可以創建一個虛根 \(k\)，使得有右區間 \([k+1,r] \to [k,r]\)，這樣子有了虛根之后就在虛根 \(k\) 下面劃分出多個子樹了。

于是我們可以列出轉移方程 \(dp_{l,r}=\sum\limits_{k}dp_{l+1,k} \times dp_{k,r}\)。轉移條件是 \(a_{l+1}<a_{k+1}\) 或 \(k=r\)，為了滿足先遍歷小編號兒子的要求。

ZROI2835.羅生門

不要被題目形式所迷糊，冷靜分析一下，或者寫個程序輸出一下發現是 \(a_i\) 行 \(i\) 的二進制表示拼接在一起。

如果是 \(n \times n\) 的積和式的話狀壓 dp 是可以解決的，但是這個做法在本題沒有前途。不過問題同樣可以考慮容斥，積和式很難求是因為它是 \(\sum \prod\) 的形式，導致每一行無法獨立求解，可以容斥一下變成 \(\prod\sum\) 形式。改寫一下表示，要求 \(\{1,2\dots n\}\) 在每個 \(i\) 中都出現。于是我們欽定若干不出現即可，答案就是 \(\sum\limits_{s}(-1)^{\lvert s\rvert}\prod\limits_{i}\sum\limits_{j\notin s}A_{i,j}\)

在本題做法也是容斥原理，\(\sum\limits_{s}(-1)^{n-\lvert s\rvert}\prod\limits_{選 n 行} \sum\limits_{j \in s}A_{i,j}\)。對于每一行如果對應的二進制數為 \(T\)，那一行可能產生權值的位置個數為 \(\rm popcount(T\cap S)\)。設權值為 \(i\) 的出現了 \(c_i\) 次。那么給定 \(S\) 如何求 \(c_i=\sum\limits_{\rm popcount(T_j\cap S)=i}a_j\)。我們設 \(dp_{i,j,s}\) 表示考慮了 \([0,i-1]\) 位，當前有 \(j\) 個 \(1\)，\(s\) 是由 $[i,n] $ 為原數，\([1,i-1]\) 位為和 \(S\) 按位與之后的結果，的 \(\sum a\)。初始值是 \(dp_{0,0,s}=a_s\)，每次不斷縮短 \(s\) 即可。

某一行每一行可以選擇的有 \(i\) 個，乘法原理即可。注意這個容斥的時候由于一共有 \(n\) 行我們卻只選了某些列，所以允許列重復出現。用生成函數解決一下就是

直接生成函數部分二項式定理計算為 \(O(2^nn^3)\)，其中容斥是 \(O(2^n)\)，計算是 \(O(n^3)\)。

通過先取 ln 再反過來 exp 可以做到 \(O(2^nn^2)\) 來計算。

ABC180F Unbranched

一道很好的計數練習題。

首先最大值恰好為 \(L\)，可以容斥為 \([\le L]-[\le L-1]\)。

對于加入鏈/環的系數是顯然的，需要注意對于二元環特判一下。

對于節點標號問題，要用 "欽定包含 \(1\)" 節點的思想，同時對于 \((i-k)\to i\) 的過程，不要從全局 \(1-n\) 的編號來考慮，而是從局部考慮，因為編號后在后續轉移中分配。我們需要找到 \(k\) 個編號分給新加入的點，然后用剩下 \(i-k\) 個編號給之前的點（之前的點已經內部分配過編號了），同時由于欽定了 \(1\)，所以系數就是 \(i-1\choose k-1\)。

AGC030F Permutation and Minimum

二重匹配問題（數字對，還有數字和位置），考慮去掉一重匹配。我們以數數匹配為主體，那么已經確定了至少一個的數對顯然不用加入匹配，只需要考慮兩個位置都沒確定的數對，最后乘以一個 \(cnt!\) 即可。

考慮進行值域從大到小掃描 dp，這樣子我們就能在后加入的數中確定 \(\min\)。

然后就是經典的記錄 "差了幾個待匹配" 的匹配法。

設 \(dp_{i,j,k}\) 表示掃到了值域 \(\ge i\)，有 \(j\) 個確定了位置的待匹配，有 \(k\) 個未確定位置的待匹配。

注意兩個未確定位置的匹配的時候，系數為 \(1\)，因為位置會在最后的階乘中確定，一個未確定位置的尋找確定位置的，系數為 \(j\)，因為這個 \(\min\) 會直接帶來貢獻，需要決定位置。一個確定位置的尋找未確定位置的系數也是 \(1\)，因為位置已經確定了。

XYD3756.區間排序

有 \(n\) 段長度為 \(n\) 的區間 \([l_i,l_i+n]\)，一個區間的權值為其左端點或者右端點，對于 \(2^n\) 種給區間賦權值的方案，求出有多少本質不同的排名。\(n\le 10^6,l_i\le 10^{12}\)。

設 \(f_i\) 表示前 \(i\) 個區間的答案。

對于第 \(i\) 個區間，它有左右端點的兩種選擇，于是就是 \(f_i\gets f_{i-1}\times 2\)。

但是這兩種方案也會有重疊，考慮什么時候 \(l_i\) 和 \(r_i\) 不可區分。那么對于所有 \(j<i,r_j>l_i\) 的 \(j\)，我們都要欽定選取左端點，同時記第一個不滿足的位置為 \(l\)。對于所有 \(j>i,l_j<r_i\) 的 \(j\)，我們都要欽定選取右端點，記最后一個滿足的位置為 \(r\)。

那么容斥一下，\(f_r\gets f_r-f_l\)。注意計算過程中的這些 \(f\) 數組都是錯誤的，只有 \(f_n\) 是正確的。因為中間的有些不合法的放在了后面去扣除。如果在當下扣除的話，會被后續重復扣除。

這題的思想很巧妙，借助 \(i\) 當跳板去轉移另外兩個位置 \(l,r\) 的 dp 值。

ARC146C Even XOR

看到異或和為 \(0\)，就要去想線性基！然后就會想到本題的第一個 key point。

可以發現集合內的大小其實不會太大，如果 \(\lvert S\rvert >n+1\)，那么其大小為偶數的集合個數 \(>2^{n}\)，而我們的值域大小是 \(2^n\)，此時選出兩個偶數大小集合合并在一起（如果遇到相同元素就不合并），這個時候的新集合就是大小為偶數且異或和為 \(0\)。

這個時候可以采用增量法對于集合大小進行 dp。設 \(dp_{i}\) 表示目前選擇了大小為 \(i\) 的集合的方案數。

對于 \(dp_1\) 就是 \(2^n\)，考慮現在已經算出了 \(i\) 的答案，加入一個元素使得集合大小變成 \(i+1\)，能加入當且僅當其值不等于其中某個奇數大小集合的值。于是只要拿 \(2^n-\) 奇數大小集合的取值個數。同樣的我們可以發現奇數集合內部的值也是兩兩不同，否者合并之后也就是一個為 \(0\) 的偶集合。所以直接把取值個數轉化到集合個數上。轉移的時候直接乘上系數就行了。

由于我們在加入數字的過程中相當于欽定了一個順序，所以最后要除以上一個階乘。

P3214 [HNOI2011] 卡農

直接做會發現這個東西異常困難。

直接 DP 本質是要記錄選了 \(i\) 后的某個中間狀態。這里我們直接令選擇 \(i\) 個之后就合法了，這樣子就不需要記錄狀態了，然后使用增量法去求解。太巧妙了。

設 \(f_i\) 表示選擇了 \(i\) 個數合法的方案數。嘗試加入一個數。我們先令這些數是一個排列而不是集合，最后除以 \(n!\) 即可。（注意增量法求出來的方案數都是排列，因為我們欽定了加入的順序）。

首先 \(i+1\) 個變量，自由元個數是 \(i\) 的，因為剩下一個可以通過異或和為 \(0\) 唯一確定。于是有 \(A_{2^n-1}^i\) 這個無約束的答案。此時有兩種不合法的情況，一個是前 \(i\) 個數異或和為 \(0\)，導致 \(a_{i+1}=0\)，另一個是存在 \(a_i\) 相等的情況。

第一種情況的方案數恰好是 \(f_i\)，直接扣去即可。

第二種情況，由于上文講了這些數是一個排序，所以是有下標的，于是我們先要選擇一個下標。有 \(i\) 種選法，選出來了 \(a_{i+1}=a_j\)，注意到此時 \(a_{i+1}\oplus a_j=0\)，所以剩下 \(i-1\) 個數構成一個合法方案，方案數為 \(f_{i-1}\)。注意到此時 \(f_{i-1}\) 只包含了那 \(i-1\) 個數的選值要求，并沒有包含住 \(a_j\) 的取值要求，所以我們要為 \(a_j\) 分配權值，由于說了前 \(i\) 個數互不相等，所以 \(a_j\) 有 \(2^n-1-(i-1)\) 種選法。

預處理下指標為定值的組合數后 dp，時間復雜度 \(O(n)\)。