雜2

P9108

較火的題。

設(shè) \(f_{i,l,r}\) 表示第 \(i\) 行涂 \([l,r]\) 的方案數(shù)，\(sum_i=\sum\limits_l\sum\limits_r f_{i,l,r}\)。轉(zhuǎn)移

\[f_{i,l,r}=sum_{i-1}-\sum\limits_{R<l}\sum\limits_{L} f_{i-1,L,R} - \sum\limits_{R}\sum\limits_{L>r} f_{i-1,L,R} \]

再設(shè) \(fl_{i,l}=\sum\limits_{R<l}\sum\limits_{L} f_{i-1,L,R}\)，\(fr_{i,r}=\sum\limits_{R}\sum\limits_{L>r} f_{i-1,L,R}\)。

有轉(zhuǎn)移

\[fl_{i,l}=fl_{i,l-1}+\sum\limits_{L\le R=l-1} sum_{i-1}-fl_{i-1,L} - fr_{i-1,R} \]

\[=fl_{i,l-1}+\sum\limits_{L\le R=l-1} sum_{i-1}-\sum\limits_{L\le R=l-1} fl_{i-1,L} - \sum\limits_{L\le R=l-1} fr_{i-1,R} \]

隨便優(yōu)化，\(O(nm)\)。

P10681

考慮若 \(A_{i,j}=1\) 則連邊 \((i,j+n)\)，那么最后形成若干個環(huán)或鏈的二分圖。

預(yù)處理 \(f_{i,0/1}\) 表示一邊放 \(i\) 個點，另一邊放 \(i-(0/1)\) 個點組成連通塊的方案數(shù)。有

\[f_{i,1} = f_{i-1,0}\times \frac{2i}{2i+1} \times i \times \frac{1}{2} \]

\[f_{i,0} = 2\times f_{i,1} \times i \times \frac{2i+1}{2i} \]

即

\[f_{i,1} = i! \times(i-1)! \times \frac{1}{2} \]

\[f_{i,0} = i! \times(i-1)! \times (2i+1) \times \frac{1}{2} \]

設(shè) \(F_{i,z}\) 表示左邊 \(i\) 個點右邊 \(z\) 個點方案數(shù)，三個轉(zhuǎn)移。

\[1\le j \le n,F_{i+j,z+j}+=F_{i,z}\times\binom{i+j-1}{j-1}\times\binom{z+j}{j}\times f_{j,0} \]

\[1\le j \le n,F_{i+j,z+j-1}+=F_{i,z}\times\binom{i+j-1}{j-1}\times\binom{z+j-1}{j-1}\times f_{j,1} \]

\[1\le j \le n,F_{i+j-1,z+j}+=F_{i,z}\times\binom{i+j-2}{j-2}\times\binom{z+j}{j}\times f_{j,1} \]

比較相似，我們只考慮一個。

\[1\le j \le n,F_{i+j,z+j}+=F_{i,z}\times\frac{(i+j-1)!}{(j-1)!i!}\times\frac{(z+j)!}{j!z!}\times (j!) \times (j-1)! \times (2i+1) \times \frac{1}{2} \]

\[+=F_{i,z}\times\frac{(i+j-1)!}{i!}\times\frac{(z+j)!}{z!} \times (2j+1) \times \frac{1}{2} \]

發(fā)現(xiàn)和 \(j\) 有關(guān)的只有 \((2j+1)\)，是可以兩遍前綴和優(yōu)化的。

做到 \(O(n,m)\)，可能需要細致的邊界處理。

P5400

從小到大填入每個極大的數(shù)。
設(shè) \(f_{i}\) 表示欽定了 \(i\) 個極大的數(shù)的方案數(shù)。為了方便設(shè) \(g_{i}=(n-i)(m-i)(l-i)\)。

有

\[f_{i}=f_{i-1}\times g(i-1)\times \binom{g(0)-g(i)-1}{g(i-1)-g(i)-1}\times (g(i-1)-g(i)-1)! \]

再

\[f_{i}=f_{i}\times \binom{g(0)}{g(i)} \times g(i)! \]

答案為

\[\frac{1}{g(0)!} \times \sum_{i\in[k,n]} (-1)^{i-k} \times f_{i}\times \binom{i}{k} \]

計算 \(g!\) 較慢，于是優(yōu)化式子。

\[f_{i} = \binom{g(0)}{g(i)} \times g(i)!\times \frac{f_{i-1}}{\binom{g(0)}{g(i-1)} \times g(i-1)!}\times g(i-1)\times \binom{g(0)-g(i)-1}{g(i-1)-g(i)-1}\times (g(i-1)-g(i)-1)! \]

\[= \frac{g(0)!}{g(i)!(g(0)-g(i))!} \times g(i)!\times f_{i-1}\times \frac{g(i-1)!(g(0)-g(i-1))!}{g(0)!} \times \frac{1}{g(i-1)!}\times g(i-1)\times \frac{(g(0)-g(i)-1))!}{(g(i-1)-g(i)-1)!(g(0)-g(i-1))!}\times (g(i-1)-g(i)-1)! \]

\[= \frac{1}{(g(0)-g(i))} \times f_{i-1}\times g(i-1) \]

可以做到 \(O(n)\)。

AT_agc064_d

考慮什么串是合法的。不妨觀察這個操作的過程。

你可以認(rèn)為 B 是一個棧。每次找到一個 R 要把它放入到一個它后面的棧中，每次找到一個 B 也要把它放入后面的棧中。

發(fā)現(xiàn)如果把 B 放入后面的棧，相當(dāng)于這個棧當(dāng)前最頂層的 R 的數(shù)量已經(jīng)確定了，這段 RRRRRB 一定對應(yīng)結(jié)果串的一段 RRRRB。而再在這個放入棧后面加 R 就和在原棧中加 R 一樣了。

所以條件轉(zhuǎn)為每次遇到 B 都要有可以定下來的 RRRRB 棧。于是貪心的填，即把結(jié)果串除了最后一段 RRRRRB 的 R 的數(shù)量排序，要求遇到 B 時之前的 R 都能塞滿一個新的結(jié)果串中的下一個 RRRRB。

設(shè) \(f_{i,j,k,l}\) 表示放了 \(i\) 段 RRRRB，當(dāng)前最長的一段長 \(j\)，一共長 \(k\)，最長的一段當(dāng)前放了 \(l\) 段。

\[f_{i,j+1,k,0}+=f_{i,j,k,l} \]

\[f_{i,j,k+j,l+1}+=f_{i,j,k,l}\times \frac{1}{k+1}\times (m-i) \]

其中 \(m\) 表示 B 的個數(shù) -1。

P11270

相交的情況直接哈希算掉。

不交可以根號分治，小于根號的串，我們可以先暴力 DP 把它推到根號長度。大于根號的暴力翻折容斥。

P10104

容斥。考慮枚舉邊集 \(S\) 并欽定 \((u,v)\in S,b_u=b_v\)，容斥系數(shù) \((-1)^{|S|}\)。選擇的邊把圖化成若干 \(b\) 相等連通塊，每個連通塊的限制變?yōu)?\(\min a_u\)，問題轉(zhuǎn)化到 \(m=0\)。

\(m=0\) 的話可以考慮枚舉從高位到低位從前到后第一個突破上界限制的數(shù)是哪一個，之后除了那個數(shù)以外任選的，用那個數(shù)調(diào)整異或結(jié)果即可。

稱每種選邊方案實際在限制 \(b\) 的點為關(guān)鍵點（每個奇數(shù)連通塊有一個點），問題變?yōu)橛嬎闼嘘P(guān)鍵點集對應(yīng)所有選邊方案的容斥系數(shù)的和。

首先我們只關(guān)心連通塊，設(shè) \(h_S\) 表示點集 \(S\) 組成聯(lián)通塊的所有塊內(nèi)選邊方案的容斥系數(shù)和。

繼續(xù)考慮容斥計算 \(h\)，即：邊任選方案 \(-\) 不連通方案。

結(jié)論：對于一個不為空的邊集，其所有選法容斥系數(shù)為 \(0\)，空集為 \(1\)。證明考慮選擇一條邊觀察，它選或不選時其他邊選擇方案一一對應(yīng)且互為相反數(shù)。

于是我們考慮如何計算不連通答案。枚舉 lowbit 所在連通塊，即子集 \(T\)，此時我們已經(jīng)計算了 \(h_T\)。再讓剩下的部分任選，即使用上述結(jié)論。不難發(fā)現(xiàn)此時我們已經(jīng)不重不漏計算所有情況。至此完成 \(h\) 的計算。

繼續(xù)計算，設(shè) \(f_S\) 表示關(guān)鍵點集為 \(S\) 時：所有連通塊構(gòu)成關(guān)鍵點集合為 \(S\) 的方案的容斥系數(shù) \(\times\) 該方案偶數(shù)連通塊任選的方案數(shù)。

轉(zhuǎn)移考慮從小到大加入點。對于當(dāng)前加入的點，小于它的點狀壓是否為關(guān)鍵點，大于它的點狀壓是否已經(jīng)被選入連通塊。有兩種轉(zhuǎn)移：

這個點是關(guān)鍵點，枚舉以它作為最小值，點數(shù)為奇數(shù)的子集 \(T\) 轉(zhuǎn)移 \(f_S=\sum f_T\times h_T\)。
這個點是不是關(guān)鍵點。
1. 這個點之前已經(jīng)被選入連通塊，直接轉(zhuǎn)移。
2. 枚舉以它作為最小值，點數(shù)為偶數(shù)的子集 \(T\) 轉(zhuǎn)移 \(f_S=\sum f_T\times h_T\times (a+1)\)。

至此完成 \(f\) 的計算。

接下來枚舉集合做 \(m=0\) 就好了。時間復(fù)雜度 \(O(n3^n)\)。

posted on 2025-01-20 10:11 lizhous 閱讀(44) 評論(0) 收藏舉報

刷新頁面返回頂部