总结于2022年8月11日，保存到文章。附图片。

图片链接

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

文字内容

数列

求数列第n项问题

杨辉三角

打印杨辉三角

通过组合数求

通过两两累加上一行求

查找某个数是否在杨辉三角内

斐波那契数列

暴力递归法

O2^n

记忆化搜索

O(n)

动态规划法

O(n)

矩阵快速幂

O(logN)

斐波那契数列套路：后面的项严格满足前面的项，都可以搞成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的整数

尾数循环问题

最后一位60项一循环

2022蓝桥国赛B组python题A

最后两位300项一循环

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

类斐波那契数列

求F(n)

矩阵快速幂 O(logN)

求累乘矩阵M

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

设一个系数k阶方阵M，系数字母表示，M·(前面很多项)转置 = (后面一些项)

每次矩阵乘法，相当于把结果项往右推移，多试几项求解方程组，得到M的所有数

求M的n-k次方

n转化成二进制，结果矩阵从E矩阵开始累乘

M本身自己也在累乘，在遍历二进制位的时候

迭代得到：M, M², (M²)², ((M²)²)²

结果矩阵根据当前二进制位看要乘当前(M^?)吗

M的n-k次方 乘  列向量

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

系数有负号，兔子两年后产小兔，五年后死亡，同理可解决

阶乘数列

递归法求阶乘

O(n)

动态规划法求阶乘

O(n)

求数列前n项和(差)问题

1/n求和

数列发散

求pi

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

随机模拟法

在一个正方形中以一条边为R画一个四分之一圆，生成随机点，统计圆内点数量

求e

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

等差

1+2+3+4+...

(首项+末项)*项数 >>1

通常用于将线性时间压缩成O1时间

n(n+1)>>1

等比

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

a首项，q公比

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

1²+2²+3²+4²....

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

2021冬季ACM校赛题

1³+2³+3³+4³....

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

前n项和公式的平方

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

暴力算法

O(N²)

for循环中记录i!, 下一项直接累乘，累加最终结果

O(N)

斐波那契数列

奇数项求和

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

最快O(1)

偶数项求和

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

最快O(1)

每一项²，累加求和

a1²+a2²+...an²

an*a(n+1)