LOJ575 不等關系

考慮只有 \(<\) 和 \(？\)的時候的做法，直接就是集合劃分了，也就是 \(\dfrac{(n+1)!}{\prod len_i!}\)。

于是直接把大于號容斥掉就行了，替換成 \([?]-[<]\)，每次替換成 \(?\) 有一個 \(-1\) 的系數。

考慮帶著容斥系數 dp，\(n!\) 最后乘，中間記錄 \(\dfrac{1}{len!}\) 的貢獻即可。記錄一下連續段的長度就可以做了，我們設 \(dp_{i,j}\) 表示考慮了前 \(i\) 個位置，當前 \(<\) 連續段的長度為 \(j\)。如果 \(<\) 的時候，直接在之前的連續段后加上一個數，\(dp_{i,j}\gets dp_{i-1,j-1}\times \dfrac{1}{j}\)。遇到 \(>\) 的時候，我們有兩個選擇，一個是替換成 \(?\)，那么有 \(dp_{i,1}\gets \sum\limits_{j} dp_{i-1,j}\)；另一種選擇是替換成 \(<\)，需要乘上 \(-1\) 的系數，\(dp_{i,j}\gets -dp_{i-1,j-1}\times \dfrac{1}{j}\)。

暴力 dp 是 \(O(n^2)\) 的。有第二個維度的存在好像不太好優化，索性直接拋棄掉第二個維度，每次選擇極長 \(<\) 段轉移，內部欽定了幾個 \(>\) 變成 \(<\) 號，就乘以對應的 \(-1\) 次冪。

可以發現這是一個分治 NTT 的形式，可以做到 \(O(n\log^2 n)\)。

CF1553I Stairs

可以根據 \(a\) 數組將 \(p\) 劃分成 \(m\) 個段，每個段內都是連續上升或者連續下降的。

有一個很直觀的式子就是 \(2^mm!\)，可是隨意放置會導致有些段出現接起來的情況，所以算多了。

考慮弱化版，也就是階梯必須是升序的，我們可以用容斥，欽定若干個段連起來，最后用 \(m'~!\) 來計算。如果加上降序情況，可以發現一個升序和降序的是不能接在一起的，只有單調性相同的可以拼接，同時注意長度為 \(1\) 的階梯具有升序和降序的兩個性質。假設最后有 \(A\) 個長度 \(>1\) 的，\(B\) 個長度為 \(1\) 的，那么方案數就是 \(2^A(A+B)!\)。

有了上述觀察，就可以先 dp 一下了，設 \(dp_{i,j}\) 表示考慮了前 \(i\) 個段，目前得到了 \(j\) 個連續段。當 \(b_i=1\) 且 \(i-1=k\) 的時候，\(dp_{i,j}=dp_{i-1,j-1}\)，否則有 \(dp_{i,j}=dp_{k,j-1}\times 2\)。最后的答案就是 \(\sum\limits_{i=1}^m(-1)^{m-i}i!dp_{m,i}\)。暴力做是 \(O(n^2)\) 的。

考慮分治，設 \(f_{i,0/1,0/1}\) 表示當前劃分了 \(i\) 個連續段，最左的/最右的是否長度為 \(1\)。合并左右兩個區間的時候可以發現這是一個卷積形式，直接使用 NTT 即可。時間復雜度 \(O(n\log^2 n)\)，由于單次要合并 \(4\times 4\) 個 dp 數組，所以常數很大。

P8340 [AHOI2022] 山河重整

約束條件是 \(\forall k\)，對于 \(\le k\) 的數，能湊數 \([1,k]\) 之內的所有數。

\(O(n^2)\) 是很好做的，直接設 \(dp_{i,j}\) 表示用前 \(i\) 個數，湊出了和 \([1,j]\) 的方案數，直接刷表法轉移就行了，注意轉移的時候需要滿足 \(j\ge i\)。

直接優化這個 dp 很難做，于是考慮用容斥扔掉若干限制條件。我們先去掉 \(j\ge i\) 的約束，于是直接設 \(f_i\) 表示前 \(i\) 個數滿足條件且和恰好為 \(i\) 的方案數。這樣子答案就是 \(2^n-f_i\times 2^{n-i-1}\)，每個不合法方案會在第一次不合法的時候被刪掉。

對于 \(f\) 的轉移，還是類似的思想，設 \(g_i\) 表示不需要滿足條件單純用 \([1,i]\) 中的若干個數湊成 \(i\) 的方案數。那么有，\(f_i=g_i-\sum f_j\times val(j,i)\)，其中 \(val(j,i)\) 表示用 \([j+2,i]\) 中的數湊出 \(i-j\) 的方案數。

對于 \(g\) 的轉移是由于和為 \(n\) 的若干個不同的數最多有 \(O(\sqrt n)\) 個。將整個圖畫成階梯狀之后做一個完全背包即可，注意選擇的數不重復，所有轉移約束。

對于 \(val(j,i)\times f_j\) 的轉移還是類似于 \(g\) 的，首先貢獻不是 \(1\)，而是 \(f_j\) 了，而且我們需要加上 \(\ge j+2\) 的基礎部分，也就是 \((j+2)\times i\)，由于是湊成 \(i-j\)，所以還需要手動 \(+j\)，那就是 \((j+2)\times i+j\)。

注意這個 \(f\) 轉移是半在線的，采用倍增優化轉移就行了。復雜度是 \(O(\sum \dfrac{n\sqrt n}{2^i})=O(n\sqrt n)\) 的。

P11458 [USACO24DEC] All Pairs Similarity P

如果只有分子的話，就是對于每一位拆貢獻就行了。

推廣到有分母的情況，還是拆分子貢獻，枚舉分子每一位把該位置有 \(1\) 的分母放在一起處理。

于是對于分母，我們只需要算出 \(\dfrac{1}{\vert a_i\cup a_j \vert}\) 的貢獻就行了，因為對于分子我們已經拆掉貢獻了（其實這一步是可以通過 \(\vert a_i\cap a_j\vert=\vert a_i\vert+\vert a_j\vert-\vert a_i\cup a_j\vert\) 直接去掉分母的，不過未必能注意到）。

先是做一步轉化，將 \(a_i\) 按位取反，那么貢獻也發生了變化 \(\dfrac{1}{\vert a_i\cup a_j \vert}\to \dfrac{1}{k-|a_i\cap a_j|}\)，考慮 \(j\to i\) 的貢獻，可以發現 \(a_i\cap a_j\) 是 \(a_i\) 的子集，也是 \(a_j\) 的子集。所以貢獻法的流程應該是 \(a_j\) 貢獻給自己的所有子集，\(a_i\) 再從自己所有的子集中求和。

不過這么做肯定會算重的，具體來說 \(\sum\limits_{s\subset a_i\cap a_j} \dfrac{1}{k-|s|}\) 被我們計算了多次。而我們只希望其貢獻出 \(\dfrac{1}{|a_i\cap a_j|}\)。因此設計出一個容斥系數 \(f(|s|)\) 和貢獻函數 \(g(|t|)=\dfrac{1}{k-|t|}\)，我們希望 \(\sum\limits_{s\subset t}f(|s|)=g(|t|)\)，也就是說 \(\sum\limits_{j=0}^i{i\choose j}f_j=g_i\)。\(k\) 很小，所以這個式子是可以 \(O(k^2)\) 遞推的。

于是我們只需要對于 \(a_j\) 的所有子集 \(s\) 都加上 \(f(|s|)\)，再對于 \(a_i\) 的所有子集求和即可。

對于前者就是對于超集做一遍高維前綴和，后者就是對于子集做一遍高維前綴和。問題就做完了。

時間復雜度 \(O(nk+k^22^k)\)。

ABC306Ex Balance Scale

假設沒有 '=' 的時候，就是一個 DAG 定向了。

需要每次剝離一個獨立集，這樣子去掉之后還是一個 DAG，就可以 dp 一層一層來解決。按理來說每次必須剝離干凈，但是這樣子太難轉移了，所以只能容斥，系數是 \((-1)^{|T|+1}\)。

其中 \(T\) 是一個獨立集。思考這個系數為何正確，上面說了在一次直接剝離干凈的時候直接去掉是正確的，設這個需要被剝離干凈的集合為 \(U\)，我們枚舉的 \(T\)，都是其非空子集，我們需要 \(\sum\limits_{T\subset U}f(|T|)=1\)。對于 \(U\) 其大小為奇偶的子集是一樣的，由于我們不考慮空集，所以奇子集比偶子集多 \(1\)，于是奇數子集產生 \(1\) 的貢獻，偶數集合產生 \(-1\) 的貢獻就行了。

有 '=' 的時候就是相當于將相鄰 "=" 點也就是一個聯通塊縮成一個點，這樣子我們就不要求加入獨立集了，加入的點集中有若干聯通塊，對于單個聯通塊看成縮成一個點，于是原本系數中的點集大小 \(|T|\) 變成了聯通塊數。也就是聯通塊數 \(+1\) 就行了。

P10221 [省選聯考 2024] 重塑時光

CF2048G Kevin and Matrices

經典將值域縮小到 \(\{0,1\}\)，然后再轉化為計算不合法情況就是每行都有 \(1\)，且每列都有 \(0\)。很容易算出方案數。

掃描值域，設置 0/1 的做法會算重。

P10064 [SNOI2024] 公交線路

考慮如何判定，對于每個點 \(u\) 求出可以一步到達的所有點集合 \(S_u\)，那么要求對于 \(\forall (u,v)~S_u\bigcap S_v\neq \emptyset\)，最緊的限制條件是葉子，所以可以將上述判定點的類型設置為葉子。

注意到這是一顆樹，且任意兩個葉子所對應的聯通塊之間交集非空，可以推廣為所有葉子的交集是一個聯通塊。

對于聯通塊計數，可以用點減邊容斥。求出每個點合法的方案數之和，減去每條邊合法的方案數之和。

直接做的話，在遇到一條路徑兩個端點都是葉子的時候不好處理，于是再次容斥。欽定不經過若干葉子。對于單點是 \(O(n^2)\) 的。全局 \(O(n^3)\)。

每次扔掉一個子樹，就可以做到樹上背包的復雜度。

反射容斥

相比于卡特蘭數的格路行走，這次的要求是不能經過 \(y=x+a\) 和 \(y=x-b\) 兩條線。

考慮交替碰到兩條線的序列，ABABAB...，BABABA... 和空串。前兩者產生 \(0\) 的貢獻，后者產生 \(1\) 的貢獻。

對于經過 \(A\) 或者 \(B\) 的單條線進行容斥，會多扣除經過 \(AB\) 和 經過 \(BA\) 的方案，加回來經過 \(AB\) 和經過 \(BA\) 的方案，又會多加上經過 \(ABA\) 和經過 \(BAB\) 的方案......

與 \(AB\) 相交的方案數，就是以 \(A\) 為對稱軸翻折終點和線 \(B\)，再以翻折過后的 \(B'\) 為對稱軸再次對稱得到最后的終點。其他 AB 組合也是以此類推。

按照上述做法進行容斥，答案就是 \(\sum\limits_{k\in Z}{n+m\choose n-k(a+b)}-\sum\limits_{k\in Z}{n+m\choose n-k(a+b)+a}\)。

注意上述 \(k\) 可以取到負數，而且前后兩個式子 \(k\) 的范圍是不同的。

可以 \(O(n)\) 預處理，\(O(\dfrac{n}{a+b})\) 進行單組回答。

gym104053J. Math Exam

給定一個長度為 \(n\)，值域在 \(\{-1,1\}\) 之間的序列，求任意前綴和在 \([0,m]\) 之間的方案數。

轉化一下就是要求行走過程中始終滿足 \(x-m\le y\le x\)，我們枚舉最后的終點共計 \(m\) 個，單次求解復雜度 \(O(\dfrac{n}{m})\)，總復雜度就是 \(O(\dfrac{n}{m}\times m)=O(n)\)。