總結(jié)于2022年8月11日，保存到文章。附圖片。

圖片鏈接

https://s1.ax1x.com/2022/08/11/vGVacV.png

文字內(nèi)容

數(shù)列

求數(shù)列第n項問題

楊輝三角

打印楊輝三角

通過組合數(shù)求

通過兩兩累加上一行求

查找某個數(shù)是否在楊輝三角內(nèi)

斐波那契數(shù)列

暴力遞歸法

O2^n

記憶化搜索

O(n)

動態(tài)規(guī)劃法

O(n)

矩陣快速冪

O(logN)

斐波那契數(shù)列套路：后面的項嚴格滿足前面的項，都可以搞成logN

通項公式

O(1)

fib(n)=(p^n-q^n) / √5

p=(1+√5)/2

q=(1-√5)/2

混淆：(√5-1)/2 是黃金分割比

另一種求法

O(1)

[ ?( ?(1+√5)/2 ?)^n ?]

[d] 表示最接近d的整數(shù)

尾數(shù)循環(huán)問題

最后一位60項一循環(huán)

2022藍橋國賽B組python題A

最后兩位300項一循環(huán)

最后三位1500項，四位15000，五位150000

類斐波那契數(shù)列

求F(n)

矩陣快速冪 O(logN)

求累乘矩陣M

先看后一項是通過前面多少項累加得到的（fib是2）看k

設(shè)一個系數(shù)k階方陣M，系數(shù)字母表示，M·(前面很多項)轉(zhuǎn)置 = (后面一些項)

每次矩陣乘法，相當于把結(jié)果項往右推移，多試幾項求解方程組，得到M的所有數(shù)

求M的n-k次方

n轉(zhuǎn)化成二進制，結(jié)果矩陣從E矩陣開始累乘

M本身自己也在累乘，在遍歷二進制位的時候

迭代得到：M, M2, (M2)2, ((M2)2)2

結(jié)果矩陣根據(jù)當前二進制位看要乘當前(M^?)嗎

M的n-k次方 乘 ?列向量

注：如果是F(n)=F(n-1)+2F(n-2)-F(n-5)

系數(shù)有負號，兔子兩年后產(chǎn)小兔，五年后死亡，同理可解決

階乘數(shù)列

遞歸法求階乘

O(n)

動態(tài)規(guī)劃法求階乘

O(n)

求數(shù)列前n項和(差)問題

1/n求和

數(shù)列發(fā)散

求pi

1-1/3+1/5-1/7+1/9-...

隨機模擬法

在一個正方形中以一條邊為R畫一個四分之一圓，生成隨機點，統(tǒng)計圓內(nèi)點數(shù)量

求e

1＋1/1!＋1/2!＋1/3!＋…

等差

1+2+3+4+...

(首項+末項)*項數(shù) >>1

通常用于將線性時間壓縮成O1時間

n(n+1)>>1

等比

1+2+4+8+....

a首項，q公比

a(1-q^n) / (1-q)

12+22+32+42....

n(n+1)(2n+1)/6

2021冬季ACM校賽題

13+23+33+43....

[n(n+1)>>1]^2

前n項和公式的平方

1!+2!+3!+4!....

暴力算法

O(N2)

for循環(huán)中記錄i!, 下一項直接累乘，累加最終結(jié)果

O(N)

斐波那契數(shù)列

奇數(shù)項求和

a1+a3+a5...+a93 = a94

最快O(1)

偶數(shù)項求和

a2+a4+a6+...+a100=a101-1

最快O(1)

每一項2，累加求和

a12+a22+...an2

an*a(n+1)