P4340 [SHOI2016] 隨機序列

記 \(s_i\) 為前 \(i\) 個的和。發現 \(+,-\) 抵消。有：\(s_i=3s_{i-1}+g_{i-1}(a_i-1)\)。其中 \(g_i\) 為連續 $\times $ 的值的和。且 \(g_i=g_{i-1}\times a_i\)。

待修用矩陣維護轉移，上線段樹即可。時間復雜度 \(O(n\log n)\)。

CF1149C Tree Generator?

發現這個括號序與歐拉序類似。

對于樹上一條路徑，可以看作是括號序的一個區間，去掉合法括號匹配。那么將 \()\) 看出 \(1\)，\((\) 看出 \(-1\) 后，就相當于將區間變成兩部分，前面一部分的和減去后面一部分的和的最大值了。因為 \(u \to lca\) 都是 \()\)，\(lca \to v\) 都是 \((\)，且 \((,)\) 抵消。

線段樹維護即可。時間復雜度 \(O(n\log n)\)。

P4425 [HNOI/AHOI2018] 轉盤

我的 typora 沒了。不想寫了。為什么電腦死機啊。

大概就是說。我們可以倒著走，因為經過一個點多次，如果某次滿足 \(\ge T_i\)，那么最后一次一定也滿足。簡單化簡相當于求 \(\min\limits_{i=n+1}^{2n}(\max\limits_{j=i-n+1}^{i}(T_j-j)+i)\)。同時增加 \(n-1\)。且有 \(T_i -i > T_{i+n}-(i+n)\)。那么就是后綴 \(\max\) 了。單側遞歸線段樹維護即可。時間復雜度 \(O(n\log^2 n)\)。

AT_arc136_e [ARC136E] Non-coprime DAG

這么困難。

考慮 \(a,b\) 什么時候可以同時選。

1. \(\gcd(a,b)=1\)。

2. 記 \(x\) 為 \(a\) 的最小質因子，\(y\) 為 \(b\) 的最小質因子。那么 \(\lfloor\frac{b}{xy}\rfloor-\lfloor\frac{a}{xy}\rfloor =0\)。

注意到偶數最多選一個，且 \(1\) 一定能選。那么嘗試對 \(a,b\) 的奇偶性分類討論：

1. \(a\) 是偶數，\(b\) 是偶數。不行。
2. \(a\) 是偶數，\(b\) 是奇數。當 \(b-y \ge a\) 時，因為 \((b-y)\bmod 2=0\)，所以不行。否則由于 \(x=2\)，\((2y)|(b-y)\)，所以一定可以。
3. \(a\) 是奇數，\(b\) 是偶數。同情況 \(2\)。在 \(a+x \le b\) 時不行，否則可以。
4. \(a\) 是奇數，\(b\) 是奇數。如果 \(a+x \le b-y\)，則不行。因為 \((a+x)\bmod 2=0,(b-y)\bmod 2=0\)。否則可以，因為 \((b-y,y]\) 中不存在 \(xy\) 的倍數，\([a,a+x)\) 中也不存在 \(xy\) 的倍數。

那么有決策：

1. \(1\) 可以選。
2. 選出來的奇數一定滿足：\(\bigcap\limits_{i=1}^{m} [x_i-g(x_i)+1,x_i+g(x_i)-1] \ne \emptyset\)。
3. 如果選擇偶數，則選出來的偶數 \(y\) 一定滿足：$y \in \bigcap\limits_{i=1}^{m} [x_i-g(x_i)+1,x_i+g(x_i)-1] $。

枚舉交集中的一個數 \(y\)。那么所有區間包含 \(y\) 的奇數都可以選，\(y\) 在其是偶數是也可以選，\(1\) 可以選。則需要維護區間加，全局 \(\max\)。差分做到 \(O(n)\)。如果帶單點修改，線段樹做到 \(O(n\log n)\)。

CF1210F2 Marek and Matching (hard version)

困難。

根據 Hall 定理，若 \(S\) 存在完美匹配，則一定有與 \(S\) 中某個點相連的右部節點構成的集合 \(T\) 滿足 \(|S| \le |T|\)。

考慮定義狀態函數 \(f_{s,t}\) 表示 \(s\) 為左部節點，\(t\) 為右部節點，且存在完美匹配的方案數。發現這個轉移會算重。舉個例子，合并兩個集合 \(S1+S2=S,T1+T2=T\)，在交換后仍然滿足條件，所以算重了。

如何。考慮定唯一的代表元。這里找 \(|S|-|T|\) 最大的，有多個找 \(|S|\) 最小的做代表元。證明唯一性。

那么可以考慮記 \(F(s,t)\) 為 \(t\) 與 \(s\) 中某個點相連的右部節點構成的集合的方案數，\(G(s,t)\) 為 \(t\) 與 \(s\) 不存在任意一條邊的方案數。那么有：

\(f_{s,t}=F(s,t)-\sum\limits_{s' \subset s}^{t' \subset t} f_{(s-s'),(t-t')}\times g_{s',t'} \times G(s',(t-t'))\)。這里 \(g_{s,t}\) 表示 \(s,t\) 不存在完美匹配的方案數。因為我們確定了唯一的代表元，所以在 \(s,t\) 不存在完美匹配時只會在將圖分成存在和不存在完美匹配兩部分時被計算一次，且 \(g_{s,t}\) 一定是代表元。

\(g_{s,t}=F(s,t)-\sum\limits_{s' \subset s}^{}\sum\limits_{t' \subset t}^{} f_{(s-s'),(t-t')}\times g_{s',t'} \times G(s',(t-t')) [|s'|-|t'|\ge |s|-|t|]\)。要求不算重。

時間復雜度 \(O(3^{2n})\)。