上一篇有點多就開新的了

文章目錄

• • 樹哈希
  • $wqs$二分
  • 單位根反演
  • 威佐夫博弈
  • 范德蒙德行列式
  • BEST定理
  • 平面圖歐拉定理
  • FWT轉移矩陣的推導
  • 保序回歸
  • 一些數學小結論
  • • 范德蒙德卷積
    • 乘轉加卷積
    • 斐波那契前綴和
    • 杜教篩+$\mu$
    • 單冪轉下降冪
    • 下降冪X組合數
  • 其他小技巧

---

樹哈希

額方法很多隨便找個都可以用，是有根樹的，無根樹的哈希要換根加個數據結構。
$$f_x=\sum _{y\in so{n}_x}{f}_y\times P(si{z}_y)$$
$P(x)$是一個不重的函數就行來，可以用$p^x$，第$x$個質數或者${\omega }_n^x$都可以。
或者
$$f_x=si{z}_x\times \sum _{y\in so{n}_x}{f}_{y}P(i)$$
不過這個的$f_y$需要按照大小排序（不然就是有序的兒子了）

---

$wqs$二分

一種二分斜率的方法。

對于一個有限制的凸函數問題（求最大值但是斜率不斷減小，或者求最小值但是斜率不斷增大），我們不知道這個凸函數但是我們可以設一條直線$y=kx+b$與這個函數相切。

然后當$y=kx+b$且到我們要求的點的時候就是答案了。

主要的難點在于確定凸函數的定義和二分$k$的時候如何求出$b$的最值。

需要特別注意的一點就是$wqs$最后二分出來的結果求得的并不一定是合法的方案，可能是與合法方案答案相同的（也就是這個凸函數恰好切到一段斜率與二分相等的位置）。

常見的凸函數問題：

• 背包限制問題
• 最小生成樹限制問題
• 費用流模型問題

---

單位根反演

補一下上個手記剩下的
$$[k|n]=\frac{1}{n}\sum _{i=0}^{n?1}{\omega }_n^{i\times k}$$
一般和二項式定理套

---

威佐夫博弈

兩堆石頭可以選擇取走一堆或兩堆的相同個數，求是否先手必勝。
證明：設石頭個數$a<b$那么若$?(b?a)\times \frac{1+\sqrt{5}}{2}?=a$則后手必勝，否則先手必勝。

---

范德蒙德行列式

對于矩陣$F$
$$\left|\begin{array}{ccccc}{x}_1^0& x_2^0& ...& x_{m?1}^0& x_m^0\\ x_1^1& x_2^1& ...& x_{m?1}^1& x_m^1\\ ...& ...& ...& ...& ...\\ x_1^{n?1}& x_2^{n?2}& ...& x_{m?1}^{n?1}& x_m^{n?1}\\ x_1^n& x_2^n& ...& x_{m?1}^n& x_m^n\end{array}\right|$$

也就是$F_{i,j}=x_i^j$時，
$$\det F=\prod _{i<j}(x_j?x_i)$$

---

BEST定理

記歐拉圖$G$，記這張圖不同的歐拉回路數量為$ec(G)$那么有
$$ec(G)=t^{root}(G,k)\prod _{v\in V}(deg(v)?1)!$$
其中$t^{root}(G,k)$表示圖$G$以$k$為根的外向樹數量

---

平面圖歐拉定理

記連通無向平面圖$G$點集$V$和邊集$E$還有區域個數$F$那么有
$$V+F=E+2$$

---

FWT轉移矩陣的推導

先定義最初始的矩陣$c(i,j)$表示$FWT(x)[i]={\sum }_{j=0}^{n}c(i,j)x_j$
然后
$$FWT(A)[k]FWT(B)[k]=FWT(C)[k]$$
$$\sum _{i=0}^n\sum _{j=0}^n{A}_i{B}_{j}c(k,i)c(k,j)=\sum _{i=0}^n{C}_{i}c(k,i)$$
又有
$$C_k=\sum _{ioptj=k}{A}_i{B}_j$$
$$\sum _{i=0}^n\sum _{j=0}^n{A}_i{B}_{j}c(k,i)c(k,j)=\sum _{i=0}^n\sum _{j=0}^{n}c(k,ioptj)A_i{B}_j$$
就有
$$c(k,i)c(k,j)=c(k,ioptj)$$
然后對于每個$i,j$分位考慮然后根據$opt$的性質推出$FWT$的矩陣再求逆推出$IFWT$的矩陣就好了。

---

保序回歸

對于序列$a$，有一些形如$a_i\le a_j$的限制，把$x$變為$y$的代價為$|x?y{|}^k$，要求使得代價和最小。

常用的方法：

整體二分：考慮對于一個$mid$，把每個數設置為$mid+k(k\in \{0,1\})$，然后求解出最小答案之后繼續分$0/1$下去二分。求解的方法一般為：最大權閉合子圖（一般情況），dp等。

正常二分+單調性解決。

在$k$不是很大的情況下可以考慮斜率優化。

神必方法。

玄題待補：
#6518. 「雅禮集訓 2018 Day11」序列
P5294 [HNOI2019]序列

---

一些數學小結論

范德蒙德卷積

$$\sum _{i=0}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{m}{k?i}\right)=\left(\genfrac{}{}{0ex}{}{n+m}{k}\right)$$

乘轉加卷積

是乘轉加但是不完全是
$$n\times m=\left(\genfrac{}{}{0ex}{}{n+m}{2}\right)?\left(\genfrac{}{}{0ex}{}{n}{2}\right)?\left(\genfrac{}{}{0ex}{}{m}{2}\right)$$

斐波那契前綴和

$$\sum _{i=1}^n{f}_i=f_{i+2}?1$$

杜教篩+$\mu$

怎么說是一個挺神奇的技巧吧就是因為$\mu ?I=?$所以假設我們要求$f?\mu$的前綴和，然后$f?\mu ?I=f??$所以我們如果能快速的求$f$的前綴和就可以快速的用杜教篩求$f?\mu$的前綴和。

具體的例子比如說斐波那契數列$Fbi?\mu$，和矩陣乘法配合能有奇效的樣子

單冪轉下降冪

設
$$f(x)=\sum _{i=0}^n{a}_i{x}^i=\sum _{i=0}^n{b}_i{x}^{\underline{i}}$$
根據
$$x^n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}{x}^{\underline{i}}$$
得到
$$b_i=\sum _{j=i}^n\left\{\begin{array}{c}j\\ i\end{array}\right\}{a}_j$$
時間復雜度$O(n^2)$

下降冪X組合數

下降冪轉組合數第二項
$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\times k^{\underline{m}}=\left(\genfrac{}{}{0ex}{}{n?m}{k?m}\right)\times n^{\underline{m}}$$

---

其他小技巧

• $a+b=\min (a,b)+\max (a,b)=a|b+a\&b$
• bitset的count是$O(\frac{n}{\omega })$的！！！

總結

以上是生活随笔為你收集整理的学习手记（2021/3/19~?）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。