文章目錄

• • $\phi$的奧秘之1
  • 某不科學的知識
  • 二維費用
  • 自然の對數(shù)大法
  • 斐波那契數(shù)列與三角形
  • $BST$大法好
  • 點陣迷蹤
  • $Cayley$公式
  • 質(zhì)嚶數(shù)分解の1
  • 費馬小的妙用の1
  • 神仙の調(diào)和級數(shù)
  • 和與積的奧秘の一
  • $dp$の費用提前計算法
  • 插板法不全的大全
  • 區(qū)間の或和 帶 區(qū)間の異或

---

$\phi$的奧秘之1

$$\phi (n)=\prod (p_i(p_i?1{)}^{a_i?1})$$

---

某不科學的知識

$$\sum _{i=1}^{min\{n,m\}}{i}^2=\frac{i?(i+1)?(2?i+1)}{6}$$

數(shù)學歸納法證明:

$$\sum _{i=1}^{min\{n,m\}}{x}^2=\frac{x?(x+1)?(2?x+1)}{6}$$
$$(\sum _{i=1}^{min\{n,m\}}{x}^2)+(x+1{)}^2=\frac{x?(x+1)?(2?x+1)}{6}+(x+1{)}^2$$
$$=>\frac{(x+1)?(2?x^2+x)+6(x+1{)}^2}{6}$$
$$=>\frac{(x+1)?(2?x^2+7x+6)}{6}$$
$$=>\frac{(x+1)?(x+2)?(2?x+3)}{6}$$
$$=>\frac{(x+1)?(x+2)?(2?(x+1)+1)}{6}$$

證畢

能力測驗

---

二維費用

若要求兩種費用，一種最值的情況下另一種最值。

那么我們可以把一個數(shù)分為兩塊:

如要求$W$最大的情況下$V$最大，那么也就是要求$W?maxV+V$最大

追查壞牛奶Pollutant Control

---

自然の對數(shù)大法

有些東西要求乘積但是發(fā)現(xiàn)只有求和的算法就可以用自然對數(shù)
$$log(ab)=log(a)+log(b)$$

THE MATRIX PROBLEM

---

斐波那契數(shù)列與三角形

一個序列選擇任意三個數(shù)字都不能組成三角形那么這個序列最小的話就是斐波那契數(shù)列。

序列

---

$BST$大法好

$BST$滿足先序遍歷是單調(diào)的。

---

點陣迷蹤

一個$n?n$的點陣中
$(1,1)$到$(x,y)$的線段上有$gcd(x,y)+1$個點(包含兩個端點)。

證明

只要$x/d$和$y/d$均為整數(shù)那么$(x/d,y/d)$就是一個點
那么$d|x,d|y$
并且$d|gcd(x,y)$
那么$gcd(x,y)\ge n/d>1$

證畢

題目鏈接:
儀仗隊
能量采集

---

$Cayley$公式

證明：

先證明標號樹枝的個數(shù)
先是$n$個沒有邊的點，加入了$k$條邊后剩下的可以加邊的個數(shù)為$n(k?1)$
（從任意一個點為根，然后要連接不是這個點所在樹枝的根）
然后答案就應該是
$$\prod _{i=1}^{n?1}n(n?i)=n^{n?1}(n?1)!$$

然后不標號的話就是$n^{n?2}$

證畢

推導得

$n$個不同點的有根樹個數(shù)為$n^{n?1}$

$n$個不同點的無根樹個數(shù)為$n^{n?2}$

父子

---

質(zhì)嚶數(shù)分解の1

$$n=\prod p_i^{c_i}$$
$$?n^2=\prod p_i^{2?c_i}$$
櫻花

---

費馬小的妙用の1

$$a^{p?1}\equiv 1(modp)$$
$$?a^k\equiv a^{k\%(p?1)}(modp)$$
$$?a^k\equiv a^{k\%(p?1)}(modp)$$
并且$a$自己冪自己$b$次以后答案是$$a\#b\equiv a^{a^{b?1}\%(p?1)}(modp)$$

證明——數(shù)學歸納法

$b=1$時成立
$$(a^{a^{b?1}\%(p?1)}{)}^a$$
$$(a^{a^{b?1}\%(p?1)}{)}^{a\%(p?1)}$$
$$a^{a^{b?1}?a\%(p?1)}$$
$$a^{a^b\%(p?1)}$$

證畢
LJJ算數(shù)

---

神仙の調(diào)和級數(shù)

$$\sum _{x=1}^n\frac{1}{x}=\log (n+1)+r(n\to \infty )$$
$r$為歐拉函數(shù)$r\approx 0.5772156649$
LocalMaxima

---

和與積的奧秘の一

當$$xy=s$$時
$x+y$最大為$2\sqrt{s}$
華華教奕奕寫幾何

---

$dp$の費用提前計算法

有些題目不太方便計算到后面的時候再計算這一步要的費用。那么我們可以考慮費用提前計算法：
費用提前計算法就是計算這一步執(zhí)行后會對后面的步驟產(chǎn)生什么費用然后提前計算入$f$中
一般適用于一些一個東西需要多少時間這個東西越往后執(zhí)行就會產(chǎn)生越多的費用，一般能直接省掉一個維度或者減少一個維度的大小。

不過注意使用費用提前計算法的時候會導致過程中的$f_i$與原本設定的意思不同(因為后面的費用已計算進去了)。
清兵線

---

插板法不全的大全

長度為$n$的序列分成$k$段方案數(shù)時$C_{n+k?1}^{k?1}$(每段可以為空)
長度為$n$的序列分成$k$段方案數(shù)時$C_n^k$(每段不能為空)
長度為$n$的序列分成$k$段每段至少長$s$時方案數(shù)時$C_{n?k?(s?1)}^k$
小a的強迫癥

---

區(qū)間の或和 帶 區(qū)間の異或

$$sum(orxora)=(sum(or)\&～a)|(～sum(and)\&a)$$
$$sum(andxora)=(sum(and)\&～a)|(～sum(or)\&a)$$
子異和

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的学习手记(2018.11.30~2019.6.6)——养老时间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。