公式
\[\sum \binom{2j}{j} \binom{2i-2j}{2j}=4^i \]\[\prod[w_i=1]={1\over 2^n} \sum\limits_S \Big( \prod\limits_{j\in S}w_j \Big) \ (w_i=\pm1) \]
\[FWT(f)=g \Longleftrightarrow g_S=\sum\limits_T (-1)^{|S \cap T|}f_T \texttt{ 可以倒著用} \]
\[\prod {1\over 1-a_iz} = \sum c_i{1\over 1-a_iz} \Longleftrightarrow c_i={1\over \prod\limits_{j\neq i}(1-{a_j \over a_i})} \]
\[\texttt{the number of out-facing block buildings on a}\times\texttt{b}\times\texttt{c: } \det \big( \binom{a+b}{a+i-j}_{i,j} \big) (1 \le i,j \le c) \]
\[x^k=\sum\limits_{j=1}^k\Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} x^{\underline{j}} \\ \Rightarrow \sum i^kf_iz^i=\sum\limits_{j=1}^k \Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} \sum i^{\underline{j}}f_iz^i=\sum\limits_{j=1}^k \Big\{ \begin{matrix} k \\ j \end{matrix} \Big\}F^{(j)}(z) \]
\[(uv)^{(k)}=\sum \binom{k}{i} u^{(i)}v^{(k-i)} \\ \Rightarrow \sum G^{(i)}{z^i\over i!}=\prod\ \sum F_j^{(i)}{z^i\over i!}\quad (G=\prod F_j) \]
\[\sum\limits_{x_1,x_2,\dots,x_n>0} \Big[\sum x_i\le k\Big] (k+1-\sum x_i) \\ = \sum\limits_{a,x_1,\dots,x_n>0} \Big[a+\sum x_i\le k+1\Big] \\ = \sum\limits_{a,b,x_1,\dots,x_n>0} \Big[a+b+\sum x_i= k+2\Big] \\ = \binom{k+1}{n+1} \]
建模
一個 01 序列區間的眾數 \(\iff\) 將 0 換成 -1 后區間和與 0 的關系
ARC137E：覆寫一個區間，每個位置覆寫次數有上限，超過后無貢獻：最小費用回圈流模型
在一個 DAG 中刪去一些點，使剩下任意 3 個點不在一條鏈上：將原圖 G 復制一遍得到 G'，對于每個點 u，從 G 中的 u 向 G' 中的 u 連邊，答案即為這個新圖的最長反鏈=最小路徑點覆寫（=二分圖匹配），
一個合法的點分樹，設它的根權值為樹的深度，每個點的權值為其父節點的權值 -1，那么點分樹方案合法 <=> 任意兩個權值相同的點之間有一個權值比它們大的點
交換一個序列的相鄰兩個 01 \(\iff\) 將 0 視為向右下走，1 視為向右上走，產生的一個“谷” V 變成“峰” ^
從一個序列中刪數就變成往一個序列里加數，往一個序列里加數就變成從一個序列中刪數，一定要與出題人對著干！
思想
每當 pos 右移一位時，a 只有一個元素性質發生大的改變，其它元素平移后不變/變化相同
求“aaa中xxx的最大值”的最大值，可以列舉 aaa 中的所有 xxx，使它最大，記錄下結果，再在所有結果中取最大值
邊很稀疏的圖 （\(m-n \le 9\) 之類的）可以考慮收縮 1，2 度點，甚至收縮 3 度點進行遞回求解
Segment Tree Beats: 留坑，，，
當對一個序列的操作等與其元素之間的大小有關時，可以考慮將 \(\le k\) 的視為 \(0\)，\(>k\) 的視為 \(1\)，01 串的操作往往有一些很好的性質
對于一些作用在多個（復雜）位置的操作，可以考慮用資料結構（一般是線段樹）維護操作軸即時間軸，然后按順序列舉位置（而不是時間）
從一個字串 \(S\) 加/刪 字符變成另一個字串 \(T\)，可以考慮將操作倒過來，變成從 \(T\) 刪/加 字符變成 \(S\)，往往會取得奇效
區間放一個數查詢區間 mex：
-
區間內連續出現最遠的 → 區間取反，變為區間內“每個位置最小出現”的最大值 （貌似這是 mex 題的常見套路）
-
標記永久化：\(\max(\min(lc,v),\min(rc,v))=\min(v,\max(lc,rc))\)
AC 自動機能夠處理：\(O(\log len)\) 求出一堆串中拎出一個文本串，其它串作為模式串出現的次數（路徑 +1 fail 樹求和）—— fail 樹是一個可以與 SAM 媲美的東西
動態規劃肯定要排序，但不一定要從左到右轉移，也可以將所有轉移排序，然后一個個轉移進行，這樣可以保證轉移程序中的另一個有序性（如凸包上的斜率），此時假的轉移自然就假了，真的轉移一定能轉
對于停時問題，如果狀態轉移形成 DAG，則停時期望為所有非法狀態出現的概率 * 離開這個狀態的期望時間，（見 定理3）
當我們要數“一個 \(f\) 生成的一個 \(g\)” 的不同的 \(g\) 的方案數時，如果不同的 \(f\) 可以生成同一個 \(g\)，則應該想辦法欽定每個 \(g\) 由唯一一種方法被 \(f\) 生成，然后數這樣的 \(f\) 的個數，
隨機二分法：對于一個很大的數域，想要求第 \(k\) 大，我們隨機挑一個數計算有 \(c_0\) 個數小于它和有 \(c_1\) 個數小于等于它，若 \(c_0+1\le k\le c_1\) 則其為答案，否則根據結果左右遞回處理，次數期望即為 \(O(\log V)\) 的
時間復雜度分析小專題
\[\sum\limits_u \sum\limits_{v\in son_u} siz_v(\sum\limits_{w\ before v}siz_w) = O(n^2) \]證明：等價于每兩個點在其 LCA 處貢獻 1，自然 \(O(n^2)\)
在一個序列上以一定的規則游走，提出 \([l,r]\) 的位置所走出的序列是整個序列所走出的序列的一個子串
一堆數異或和 \(=C\) 的題目，有兩種基本方法：一是 \(FWT\)，二是如果有一個數可取的值為 \([0,2^k)\)， 則方案數可以 \(O(1)\) 計算（其它任選，這個數調整即可）
鞭尸技巧：一些互相關聯的操作，可以單獨掰出一個操作來，考慮其它操作，如果對它有影響，那就有影響；沒有影響的操作等于重開，就是干了一個空氣，剩下操作的概率相同（獵人殺）
技巧
\(mod 2\) 意義下的多項式，乘法（又稱二項卷積）可以變為子集卷積，求逆即為自身，可以各種亂搞
當一個區間的答案與其最小值/最大值有關時，可以考慮對整個序列建出笛卡爾樹，然后對每個節點預處理出其前后綴的答案，對于每組詢問 \([l,r]\)，以其最大值/最小值 \(k\) 為中心劃分成三部分：\(val(l,r),f(l,k-1),f(k+1,r)\) 計算，后兩者即為一個節點的前綴/后綴
分治 FFT 只需要保證遞回層數是 \(O(\log n)\) 級別的，例如 \(m\) 個多項式相乘，次數和為 \(n\)，盡管這些多項式次數各不相同，但直接普通分治 FFT，每層的次數和均為 \(O(n)\)，共 \(O(\log n)\) 層，則總復雜度為 \(O(n \log^2 n)\)
！！ 有些（很多）換根樹形 dp 可以對于每個“上子樹”都算出它的 dp 值，但這樣做是 \(O(n^2)\) 的（雖然界很弱），怎么辦？拆點！將一個點的若干個兒子拆成一條鏈（和邊分治一樣），然后就是 \(O(n)\) 的了（邊權的重賦值可能有點棘手）
求強連通分量中所有環長度的 \(\gcd\)，可以跑出一棵 dfs 樹，然后對所有非樹邊 \((i,j)\)，求 \(|dep_i+1-dep_j|\) 的 \(\gcd\)，
---——對于一些傳染性問題的技巧——
-
如果轉移是直至無窮時候的并且是回圈的，那么可以每次不同時轉移，而是每次只轉移一步
-
初始時每個點找出一條出邊，找不到一般很平凡，否則就成了一棵基環樹，
-
轉移的性質有時滿足：若 a -> b，那么 a 一定比 b 劣，這時，可以從每棵基環樹開始搜，搜到其它基環樹則并查集合并，否則只遇到自己，自己就是答案，
-
運用 Boruvka 演算法的復雜度分析，我們每次對于一層中所有基環樹同時開搜，這樣每輪基環樹個數至少減半，于是就是 \(O(n \log n)\) 的，
對于一棵樹，求一棵子樹內是否有某種顏色，可以將所有有此顏色的點按 dfs 序排序，每個點打標記 +1，每相鄰兩個點的 lca 打標記 -1，答案即為子樹內標記和
（因為聽說 pb 在 GDOI2019 因為不會這個技巧爆炸了所以全部加粗）
dp 神奇優化：CDQ 分治（？，\(solve(l,r)\) 遞回到 \(solve(l,k-1)\) 與 \(solve(k,r)\)，在中間處理 \([l,k-1]\) 到 \([k,r]\) 的轉移，
然后 \(k\) 不一定要是區間中點，如果能夠在 \(\min (k-l,r-k)\) 的時間內處理出這個轉移，則時間復雜度等同于啟發式合并，\(O(n \log n)\)，
復雜度分析：有時一個演算法的復雜度可能看上去是 \(O(nmk)\) 的，實際上是 \(O(nk\frac{m}{k})\) 的，然后你就過了（？
如果要求一個區間第 \(k\) 大的數的貢獻，可以轉為列舉每個位置，看它在那些區間里面是第 \(k\) 大，這個就開一個鏈表，每次查詢最小的左右兩邊 \(k\) 個位置，再把它刪掉，
解樹上的 dp 方程的好套路：\(f_u=\sum\limits_{v \in son_u} c_vf_v+d_uf_{fa_u}\)，則記 \(f_u=a_uf_{fa_u}+b_u\)，當 \(u\) 為根時就有 \(f_u=b_u\)，于是再從上到下遞推回來即可
處理點分樹的技巧：留坑
對于一個由若干條直線組成的下凸函式，可以用如下方法求出它的所有拐點：先找出最左端和最右段的直線，找出它們的交點，如果這個交點在凸殼上，則這個區間內只有這一個拐點，回傳；否則，找到這個交點橫坐標所在直線，左右遞回處理，這個程序是 \(O(n)\) 的（不會證）
若 \(a_1,a_2,\dots,a_n\) 中有 \(k\) 個子集的和為 \(j\)，則不妨設 \(a_1+a_2+\dots+a_x=j\)，有 \(a_1,a_2,\dots,a_x,-a_{x+1},-a_{x+2},\dots,-a_n\) 中有 \(k\) 個子集的和為 \(0\)，
\[x^k=\sum\limits_{j=1}^k\Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} j!\binom{x}{j} \]于是 \(k\) 次方可以表示為若干個組合數之和，這給組合意義賦予了非常好的武器，
對于計數的問題，可以考慮轉化為期望，然后變成次數較小的多項式進行插值，
dp 的批量轉移技巧：如果我們要進行若干次 dp，每次 dp 的初值相同而終態不同，則我們可以將整個 dp 反過來進行，如果原來的 dp 有 \(u*k \rightarrow v\)，則在新的 dp 中進行 \(v*k\rightarrow u\)，就可以求出 dp 的結果，僅限于一個點 dp 到另一個點的 dp，
巧妙推性質：如果我們可以從一個狀態轉移到其它若干個狀態，但每個狀態的某個函式值恰有一種轉移使之嚴格變小，且函式值均非負，則我們可以證明所有狀態都可以走到某若干個函式值最小的狀態，從而形成樹/森林/基環樹，
dp 技巧：如果一個轉移方程形如 \(f_{i,j,k}\cdot a(j) \cdot b(k)\rightarrow g_{i',j',k'}\) 之類的，其中中間的兩個轉移系數分別與某一維獨立，則可以考慮設定一個中間狀態 \(h_{i,j,k}\)，例如讓 \(f_{i,j,k}\) 轉移到 \(h_{i',j',k'}\)，再由另一種轉移從 \(h_{i',j',k'}\) 轉移到 \(g_{i'',j'',k''}\)，
無窮歸納法： 求一個序列 \(a_1,a_2,\dots,a_n\) 的函式 \(f(a_1,a_2,\dots,a_n)\)，可以對方差進行歸納，即
\[f(a_1,a_2,\dots,a_k,a_{k+1},\dots,a_n)\leftarrow f(a_1,a_2,\dots,{a_k+a_{k+1}\over2},{a_k+a_{k+1}\over2},\dots,a_n) \]由于前者的方差嚴格小于后者的方差，我們就可以無限將序列 \(a\) 變為同一個值！
（事實上，方差這個函式可以改為任意一個會嚴格變小的函式）
樹上多點最遠距離： 維護一個樹上的點集，支持加點，刪點，詢問一個（樹上的）點到點集中任意一個點的最遠距離
做法：把所有點按一定順序丟到一個線段樹里（只要有順序就行，方式任意，這意味著可以按 時間戳/dfn 排序等方式也是可行的），每個節點上維護其節點內所有點形成的虛樹的直徑端點，合并時直接6條線段取最大值即可（用 #define 好用）
查詢時直接對區間內直徑的兩個端點測一下即可（這意味著也可以只對一個 時間段/子樹 查）
樹上與點 \(u\) 距離在 \(k\) 以內的點一定在 \(u\) 的 \(k\) 級祖先的子樹內（注意判0）
拉格朗日乘子法??： 用于計算多點函式最值的方法，記住偏導以及算子 \(\lambda\)
具體公式見這里
公式2
當 \(B,C\) 中的元素值都是 \(v\) 時，可以雙重遞推計算
\[\det \begin{pmatrix} A & B \\ C & D \end{pmatrix} 與 \det_s \begin{pmatrix} A & B \\ C & D \end{pmatrix} \]（遞推到 $ \det A, \det_s A, \det D, \det_s D $ ），
其中 \(\det_s A\) 代表將 \(A\) 中任意一行全變成 \(1\) 之后求和，具體遞推方式見 這里
重點在于計算將 \(A\) 中所有數都減去 \(t\) 之后的矩陣 \(A_t\) 的 \(\det\) 與 \(\det_s\) 值，
實作
當計算中可能出現 0 的逆元時，可以考慮定義整數類 Int，存盤結果為 \(x \cdot p^y\)
將整個 bitset 翻轉（不是01反轉）過來，可以先用 to_string 轉化成字串，字串翻過來，再轉化回去（不過是 \(O(n)\) 的）
當陣列需要負數下標時，可以先找出所有負數的最小值，然后將偏移量設為這個最小值的相反數（而不是事先定義，會浪費很多空間）
卡常專題：
SegmentTree Beats 卡常技巧：當新賦的值比當前節點的 max 還大時直接 return
當回傳值只是用來計算運算式時可以定義為 static 型別并 const X& 形式回傳
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/499504.html
標籤：C++
上一篇：零基礎學Java（8）陣列
下一篇：第1章 預備知識