对于任意正整数$m,n$，有：
$$
\sum_{i=1}^n\frac{ {a_i}^{m+1} }{ {b_i}^m}\ge\frac{(\sum_{i=1}^na_i)^{m + 1} }{(\sum_{i = 1}^n {b_i})^m}
$$

西点

1.卷

原料：

• 低筋粉250g
• 鸡蛋10个
• 色拉油150g
• 水200mL
• 5%糖的奶油（用稀奶油和糖制得）
• 250g糖

步骤：

1.蛋清蛋黄分离。

2.蛋清 + 200g糖打发至“软尖锋”。

3.200mL水 + 50g糖 + 150g油搅拌至糖化掉。

4.往步骤3中的混合物中加面粉搅匀。

5.往步骤4中的混合物中加蛋黄搅匀。

6.将步骤5所得混合物和步骤2所得混合物一起搅匀（注意这里要用刮板搅拌，用翻拌和切拌的方法，减少气泡逃逸）。

7.将步骤6所得物在烤盘里铺平，送入烤箱烤。

8.将稀奶油和5%糖打法，然后将奶油均匀涂抹在烤好的蛋糕上，然后将蛋糕卷起来即可。

2.泡芙

原料：

• 黄油215g
• 鸡蛋3个
• 水160mL
• 低筋粉205g
• 糖粉96g
• 杏仁粉 30g

步骤：

1.将135g黄油，96g糖粉，30g杏仁粉，低筋粉105g搅匀，将混合物弄成棒状，放入冰箱冷冻一晚。

2.将黄油和水加热至沸（用蛋抽搅拌）

3.2中产物加热至沸后，迅速往其中导入100g低筋面粉，用蛋抽搅拌至面团装。

4.往3中产物里以此加3个鸡蛋，用蛋抽搅至面糊状。

5.将4中产物用裱花袋挤入烤盘，”一坨“就是一个泡芙。

6.将1中冷冻后的产物切片，每一个泡芙上放一片。

7.将烤盘送入烤箱。

同余

1.线性同余方程

给定整数$a,b,m$求一个整数$x$满足$ax \equiv b \pmod m$，或给出无解。

设$a \times x = b + my$，则$ax + my = b$，有解的充要条件是$gcd(a,m)|b$.

接下来只要用exgcd求出一个解，然后就可以求通解了。

2.中国剩余定理

设$m_1,m_2,m_3,……,m_n$是两两互质的整数，对于任意的$n$个整数$a_1,a_2,……,a_n$，关于$x$的方程组
$$
\begin{cases} x \equiv a_1 \pmod {m_1}\x \equiv a_2 \pmod {m_2}\……\x \equiv a_n \pmod{m_n}\end{cases}
$$
有整数解。

证明：

设$m = \prod_{i = 1}^nm_i,M_i = m / m_i$，$t_i$是线性同余方程$M_it_i \equiv 1 \pmod{m_i}$的一个解。

则$x_0 = \sum_{i = 1}^n a_iM_it_i$是一个解

因为$M_i$是除了$m_i$以外所有数的倍数，所以$\forall k \neq i,a_iM_it_i \equiv 0 \pmod{m_k}$。而因为$M_it_i \equiv 1 \pmod {m_i}$，所以 $a_iM_it_i \equiv a_i \pmod {a_i} $。

这是一个特解。通解为$x = x_0 + km(k \in Z)$。

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

  #include<iostream> #include<cstdio> #define int long long using namespace std; int n,m[30],a[30],M = 1,v[30],t[30],V1,V2; int exgcd(int a,int b,int &x,int &y) { if (b == 0) { x = 1; y = 0; return a; } int d = exgcd(b,a % b,x,y); int z = x; x = y,y = z - (a / b) * y; return d; } signed main() { scanf("%d",&n); for (int i=1; i<=n; i++) { scanf("%d %d",&m[i],&a[i]); M = M * m[i]; } for (int i=1; i<=n; i++) v[i] = M / m[i]; for (int i=1; i<=n; i++) { int x0,y0; int gcd = exgcd(v[i],m[i],x0,y0); x0 %= m[i]; if (x0 <= 0) x0 += m[i]; t[i] = x0; } int sum = 0; for (int i=1; i<=n; i++) sum += a[i] * v[i] * t[i]; sum %= M; if (sum < 0) sum += M; printf("%lld\n",sum); return 0; }

3.中国剩余定理的扩展版本

上面的方法要求$m_1,m_2,……,m_n$两两互质。现在给出一种对$m_i$没有要求的算法。

数学归纳法：假设前$k - 1$个方程已经求出了一个解$x$。记$m = lcm(m_1,m_2,……,m_{k - 1})$，则$x + i \times m (i \in Z)$是前$k - 1$个方程的通解。

考虑第$k$个方程，求一个$t$，使得$x + t \times m \equiv a_k \pmod {m_k}$。将这个方程变换一下，得到$m \times t \equiv a_{k} - x \pmod {m_k}$,求$t$.
$$
m \times t + m_{k} \times p = a_{k} - x
$$

《算法竞赛进阶指南》笔记

0x00基本算法

0X01位运算

• 计算机读入原码A，然后将读入的原码转为补码B，接下来对补码进行运算得到运算后的补码C，最后将补码C转换为原码D输出。
• 要注意%1这种特殊情况。任何数%1都是0。
• 回忆这道题：$1 \le a \le 10^{18},1 \le b \le 10^{18}$,$1 \le p \le 10 ^ {18}$,输出$a \times b$。这道题有两种解法。
• 回忆：起床困难综合症
• 写状压动规时，如果遇到不知道按照什么顺序遍历状态的情况，可以直接for (int i=0; i<(1 << n); i++)来遍历，可以保证求解后继状态时前驱状态已经求解完毕。
• 注意如果要读入一个$n$行$m$列的字符矩阵，要用$n$个字符数组来读，切忌不可用单个字符读入，在linux系统下会出错。
• x >> 1会将x向下取整，而x / 2会将x向零取整。

0x02递归与递推

• 数组要开大开大开大！！！
• 求一个数的约数和，可以先将其质因数分解。如要求$n$的约束和，质因数分解得到$n = \prod_{i = 1}^np_i ^{s_i}$，然后$n$的约数个数为$\prod_{i = 1}^n(s_i + 1)$,约数和为$\prod_{i = 1}^n \sum_{j = 0}^{s_i}p_i^j$。
• 将一个数分解质因数的时候要注意处理$ > \sqrt{n}$的质因数。这类质因数如果有就只有1个，但千万要注意！！！！

0x03前缀和与差分

• 回忆一下这道题。
• 要用abs函数的话还是引用cmath库，不要手写。手写abs函数可能会引发ambiguous编译错误。
• 回忆一下这道题。

0x04二分

• 初赛的考点。二分的写法要么是mid = (l + r) >> 1,l = mid + 1,r = mid，要么是mid = (l + r + 1) >> 1,l = mid,r = mid - 1。
• 实数域上的二分，通常eps设为$10^{-(k + 2)}$,其中$k$是要保留的小数位数。
  有时候精度不易确定，就干脆固定循环次数，可以这样写：

1
2
3
4
5
6

for (int i=0; i<100; i++) {
   	double mid = (l + r) / 2；
    	if (check(mid))
       	l = mid; else
           r = mid;
   }

• 回忆一下这道题。

• 如果你的答案是一个实数，而题目要求你向下取整，你就要小心，不能直接用floor(),因为你的浮点数会有误差，比如1.5会变成1.499999999999999999999075。所以如果题目要求你保留4位，你就直接将整个计算过程用整数来实现，同时将整数扩大1000倍来保证精度。

• 用这种写法

1
2
3
4
5
6

while (l < r) {
   	mid = (l + r) >> 1;
       if (check(mid))
       	l = mid + 1; else
           r = mid - 1;
   }

$\hspace{1cm}$ 要注意while循环外面最后还要check一下l，因为最后l也是一个可能的答案，但是你的while条件是l < r,当l = r时会扼杀这种可能性。

• 证明：对于任意有向完全图存在Hamilton路径

• 三分求单峰函数最值时，对于区间$[l,r]$,三分得到两个点$m1,m2$。则接下来枚举的是** “较差” **的那个点与离这个点较远的一个端点（l或r)构成的区间。

0x05排序

• lower_bound用法：int p = lower_bound(a + 1,a + n + 1,x) - a。注意返回的是第一个小于等于x的数的下标。

• unique用法:int p = unique(a + 1,a + n + 1) - a - 1。

• 可以用一个大根堆和一个小根堆来维护一个不断加数的序列的第$k$大数。比如这道题和这道题.

• 回忆这道题。

• 遇到要开long long的时候还是define int long long比较保险。

• 两个相邻的数之间的交换最多只会增加或减少一个逆序对，也有可能逆序对个数没有变化。Problem for this.

• 回忆一下这道题。这题的结论是：

  • 对于奇数码问题，两个局面可互相到达当且仅当将两个局面写成一维序列后两个序列的逆序对个数奇偶性相同。
  • 对于偶数码问题，两个局面可互相到达当且仅当将两个局面写成一维序列后两个序列的“逆序对数之差”和“两个局面下空格所在的行数之差”奇偶性相同。

  该结论的充分性尚未证明。

• 一个启示：一些移动问题都可以弄成一维来看，环的话可以断成链来考虑。

• 运用奇偶性时的技巧：如果操作值是累加/减的，那么使正确的操作值为偶数，因为偶数 $\pm$ 偶数 = 偶数。如果操作值是累乘,则使正确的操作值为奇数，那么这样可以保证只要一个错误的操作出现，最后的结果可以显示为错误。

0x06倍增

• 回忆这道题。
• 回忆这道题。

0x07贪心

• 回忆problem 1和problem 2和problem 3。

• problem 4
  problem5.

• vector的size()返回值是一个unsigned int,所以对其-1或减去一个数时要慎重。

0x00习题集

• 开long long!!!!!!

• problem 1

• problem 2

• problem 3

• problem 4
  (这道题虽然你做出来了，但是还是要看一下的！）

• problem 5(注意取值范围！）

0x10基本数据结构

0x11栈

• problem 1回忆这道题以及它的思想！

• 后缀表达式计算方式：

  遇到数就入栈，遇到符号就取出栈顶两数运算，并将运算结果重新入栈。

• 中缀表达式转后缀表达式：

  遇到数就输出。

  遇到左括号就入栈。

  遇到右括号就一直弹出并输出栈中符号，直到遇到左括号。

  遇到运算符，若栈顶运算符等级不低于新符号，则一直去除栈顶并输出，最后把新符号入栈。

  最后依次取出并输出栈中的剩余符号。

0x12 队列

• problem 1
• problem 2

0x13 链表

• problem 1

0x14 Hash

• problem 1
• problem 2

0x15 字符串

• p75 最小表示法

0x16 Trie

0x17 二叉堆

• problem 1
• problem 2
• problem 3

0x18 Huffman 树

• problem 1

习题集

• problem 1
• problem 2
• problem 3
• problem 4
• 算了都看一遍吧。

​
​

0x30数学知识

0x31 质数

• 阶乘分解

0x32约数

• problem1

• 神仙题

• problem2

• 欧拉函数：详见《欧拉函数学习笔记》

• problem 3

• (a & b) ^ (a & c) = a & (b ^ c)。

0x40 数据结构

• 线段树你的写法要开8倍空间！！！
• 留坑：cdq分治，莫队，可持久化数据结构

0x50动态规划

• 注意：最大值和最小值一定要初始化，不能任其为0，否则会出问题。
• 建图的first，last，nxt数组在多组数据时都要初始化！！！！

0x60图论

• 注意：hash是关键字，不要用它作为变量名或函数名！！！
• 很巧妙的一道题！

Tips

• 遇到和式一定要分开来考虑，就是说$\sum_{i = l}^ r(A + B) = \sum_{i = l}^rA + \sum_{i = l}^rB$,可以保证，分开来考虑一定更简单。

0xFF 血的教训

• 对$n$进行质因数分解时，先找到在1到根号n之间的所有质数，然后，千万不要忘记，n还可能有一个大于根号n的质因数，这个质因数可以是n，也可以不是n！

• 入队时不要写成q[--tail] = q[tail + 1];,写成这样: tail--; q[tail] = q[tail + 1];

• 后缀数组初始化要记得把sa,t1,t2都清空！还有记得c数组的大小要开到字符串长度！

• 后缀数组在build—height的时候要注意i的循环要从1开始循环，然后判断rnk[i] == 1时跳过，i循环不能直接从2开始！

正确写法见后缀数组那篇文章

• $a^b$对m取余的结果等于$a^{b % \varphi(m)}$对m取余的结果，注意加粗处是m，不是$\varphi(m)$!!

• 树状数组query时要记得return ans！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char s[105];

int main() {
	int i = 100;
	for (i=5; i<6; ++i)
		i = i;
	
	int j = 100;
	for (j=5; j>5; ++j)
		j = j;
	
	printf("i = %d\n",i);
	printf("j = %d\n",j);
	return 0;
} 

请说出输出的结果

• C++ 右移是算术右移，空出来的位用符号位补

扩展欧拉定理

扩展欧拉定理无需 a,m 互质。

结论

$$
b\ge\varphi(m)\text{时},a^b\equiv a^{\left(b\mod\varphi(m)\right)+\varphi(m)}\pmod m
$$

证明

先取$m$的一个质因数 $p$，令$m=p^r\times s$, $gcd(p,s)=1$

由欧拉定理得 $p^{\varphi(s)}\equiv1\pmod s$由欧拉函数的性质得 $\varphi(m)=\varphi(s)\times\varphi(p^r)$，所以 $p^{\varphi(m)}\equiv1\pmod s$ 。

设 $p^{\varphi(m)}=ks+1$，那么 $p^{\varphi(m)+r}=km+p^r$，所以 $p^{\varphi(m)+r}\equiv p^r\pmod m$ 。

当 $b\ge r$ 时，$p^b\equiv p^{b-r}\times p^r\equiv p^{b-r}\times p^{\varphi(m)+r}$ $\equiv p^{b+\varphi(m)}\pmod m$。

因为 $r\le\varphi(p^r)\le\varphi(m)$，所以当 $b\ge 2\varphi(m)$ 时 $b-\varphi(m)\ge r$，所以 $p^b\equiv p^{b-\varphi(m)}\pmod m$，即 $p^b\equiv p^{(b\mod\varphi(m))+\phi(m)}\pmod m$。

将 $a$ 质因数分解后乘起来，就可以得到 $a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\pmod m$.

需要注意的是，$b<\varphi(m)$ 时，$a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\pmod m$不一定正确。

高斯消元

高斯消元适用于求解线性方程组。

一般的，对于线性方程组：
$$
a_{1,1}x_1 + a_{1,2}x_2 + a_{1,3}x_3 + ……a_{1,n}x_n = b_1
$$
$$
a_{2,1}x_1 + a_{2,2}x_2 + a_{2,3}x_3 + ……a_{2,n}x_n = b_2
$$

$$
……
$$

$$
a_{n,1}x_1 + a_{n,2}x_2 + a_{n,3}x_3 + ……a_{n,n}x_n = b_n
$$

我们用下面这个矩阵来表示这个线性方程组：
$$
\left {
\begin{array}{ccccc|c}
a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1,n} & b_1 \
a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{2,n} & b_2 \
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \
a_{n,1} & a_{n,2} & a_{n,3} & \cdots & a_{n,n} & b_n \
\end{array}
\right }
$$

我们循环一个变量$i$（从$1$到$n$）

先在矩阵中找到一行（设这行是第$x$行），使得$a_{x,1},a_{x,2},……,a_{x,i-1}$都为$0$，但$a_{x,i} = 0$。

然后用这一行矩阵，用简单行变换的方式将矩阵其他行的第$i$项的系数消为0。

最后我们就得到一个“阶梯矩阵”，然后就可以愉快地求解了。

• Code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

  #include<iostream> #include<cstdio> #include<cmath> using namespace std; const int maxn = 1e3 + 5; double a[maxn][maxn],b[maxn]; int n; int main() { scanf("%d",&n); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) scanf("%lf",&a[i][j]); scanf("%lf",&b[i]); } for (int i=1; i<=n; i++) { for (int j=i; j<=n; j++) if (fabs(a[j][i]) > 1e-10) { for (int k=1; k<=n; k++) swap(a[i][k],a[j][k]); swap(b[i],b[j]); break; } for (int j=1; j<=n; j++) { if (j == i) continue; double rate = a[j][i] / a[i][i]; for (int k=1; k<=n; k++) a[j][k] -= rate * a[i][k]; b[j] -= rate * b[i]; } } for (int i=1; i<=n; i++) printf("x%d = %.2lf\n",i,b[i] / a[i][i]); return 0; }

卡塔兰猜想的一个特殊情况的证明

命题：$x,y$都是正整数，求证不存在$x>2,y>3$使得$3^x-2^y=\pm 1$

证：1° $3^x-2^y = 1$

$$ 3^x - 2^y = 1$$

$$\because x > 2,y > 3\$$

$$\therefore 设s = x - 2,t = y - 3(s \ge 1,t \ge 1)$$

$$ 则3^2 \times 3^s - 2^3 \times 2^t = 1\$$

$$ 9 \times 3^s-8 \times 2^t = 1$$

$$ \therefore 3^s = 1 + 8k,2^t = 1 + 9k (k \in Z)$$

$$ \because s \ge 1,t \ge 1$$

$$ \therefore k \ge 1$$

$$ \because 3^s = 1 + 8k （1）$$

$$ \therefore 3^s \equiv 1 \pmod 8$$

$$ 而当s = 2l(l \in Z)时，3^s \equiv 1 \pmod 8$$

$$\therefore 9^l = 8k + 1$$

$$ 又\because 2^t = 1 + 9k (2)$$

$$ 且当t = 6c (c \in Z)时，2^t \equiv 1 \pmod 9$$

$$ \therefore 64^c = 1 + 9k (3)$$

$$ 由(2),(3),有：\ \begin{cases} k \equiv 1 \pmod 9 \ k \equiv 7 \pmod {64}\ \end{cases}\ $$

$$所以k \equiv 199 \pmod{576}$$

$$ \therefore 9k + 1 \equiv 76 \pmod {576}$$

$$ 由(3) \ 则64^c = 576r + 76(r \in Z)$$

$$ \because 64 | 576,64 \nmid 76$$

$$ \therefore 无解。 $$

2° $3^x - 2^y = -1$

$$ 3^x - 2^y = -1$$

$$ 2^y - 3^x = 1$$

$$ 令s = y - 3,t = x - 2 $$

$$ 8 \times 2^s - 9 \times 3^t = 1$$

$$ 2^s = 8 + 9k,3^t = 7 + 8k (k\in Z)$$

$$ \because 3^t = 7 + 8k$$

$$ \therefore 3^t \equiv 7 \pmod 8$$

$$ 而3^t除8的余数集合为{1,3}$$

$$ \therefore 无解。$$

Q.E.D.

—–2020.1.18 20:50

关于$x^y$和$y^x$的大小判断问题的一点思考

不妨令$x < y$。

则设$x = a,y = a + b,(a > 0,b > 0)$。
$$
a^{a + b} > (a + b)^a
$$
$$
\Leftrightarrow a > (a + b) ^ {\frac a {a + b}}
$$
$$
\Leftrightarrow a > (a + b) ^ {(1 - \frac b{a + b})}
$$
$$
\Leftrightarrow a > (a + b) / ((a+b)^{\frac b{a + b}})
$$

$$
\Leftrightarrow (a+b)^{\frac b{a + b}} > (1 + \frac ba)
$$

$$
\Leftrightarrow a + b > (1 + \frac ba) ^ {\frac {a + b}b}
$$

$$
\Leftrightarrow a + b > (1 + \frac ba) ^ \frac ab \times \frac{a + b}{a}
$$

$$
\Leftrightarrow a > (1 + \frac ba) ^ \frac ab
$$

接下来对$a$,$b$进行分类讨论：

• $a > b$。则$(1 + \frac ba) ^ \frac ab < e$，所以$a$只要大于$e$，那么$x^y > y^x$.若$a <= 2$，那么$x^y < y^x$.

• $a = b$。则$(1 + \frac ba) ^ \frac ab = 2$,$a$只要大于2，$x^y > y^x$.

• $a < b$。则$(1 + \frac ba) ^ \frac ab = (1 + k)^\frac 1k ,(k > 1)$,此时易证$(1 + k)^\frac 1k < 2 ,(k > 1)$。

  反证法证明该结论：设$(1 + k)^\frac 1k = v (v \ge 2)$,则$v^k = 1 + k$。当$v = 2,k = 1时$,$v^1 = 2 = 1 + k$，而指数函数增长迅速，所以当$v = 2,k > 1$时，$v^k > 1 + k$。而$v \ge 2$,所以$v^k > 2^k > 1 + k$，两者不可能相等。

  所以此时只要$a \ge 2$，即可保证$x^y > y^x$.

微分总结

1.极限，导数，连续性，可导性

$$
\lim_{x \to a}f(x) = L
$$

$\hspace{1cm}$这个式子叫做函数$f$在$a$处的双侧极限，表示对于任意的$\varphi>0$，可以选取对应的$\beta > 0$，使得对于所有满足$0 < |x - a| < \beta$的$x$，都有$|f(x) - L| < \varphi$.

$\hspace{1cm}$除了双侧极限，我们还有左侧极限和右侧极限。
$$
\lim_{x \to a^-}f(x) = L
$$

$\hspace{1cm}$这个式子叫做函数$f$在$a$处的左侧极限，表示对于任意的$\varphi>0$，可以选取对应的$\beta > 0$，使得对于所有满足$0 < a - x < \beta$的$x$，都有$|f(x) - L| < \varphi$.

同时：
$$
\lim_{x \to a^+}f(x) = L
$$

$\hspace{1cm}$这个式子叫做函数$f$在$a$处的右侧极限，表示对于任意的$\varphi>0$，可以选取对应的$\beta > 0$，使得对于所有满足$0 < x - a < \beta$的$x$，都有$|f(x) - L| < \varphi$.

$\hspace{1cm}$极限不一定存在，比如$f(x) = sin(\frac1x)$在$x = 0$处就没有极限。

• 三明治定理：

  如果对于所有在$a$附近的$x$都满足$g(x) \le f(x) \le h(x)$，且

  $$

\lim_{x \to a}g(x) = L = \lim_{x \to a}h(x)
$$

$\hspace{1cm}$那么有
$$
\lim_{x \to a}f(x) = L
$$

• 连续性

  若$x$在函数$f$的定义域内，函数$f$在$x$处存在双侧极限，且双侧极限等于$f(x)$，则函数$f$在$x$处连续。

• 导数

  函数$f$在$x$处的导数$f’(x)$定义为：
  $$
  f’(x) = \lim_{h\to x}\frac{f’(x + h) - f’(x)}{h}
  $$
  同时我们也可以用$\frac{dy}{dx}$来表示函数$f$在$x$处的导数。其中$dx$表示$x$变化很小一个范围，$dy$表示此时$y$对应的变化量。

• 可导性

  函数$f$在$x$处可导，当且仅当函数$f$在$x$处连续，且函数$f$在$x$处的“左导数”和“右导数”相等，其中：
  $$
  左导数= \lim_{h \to x ^-} \frac{f’(x + h) - f’(x)}{h}
  $$

  $$
  右导数 = \lim_{h \to x^+}\frac{f’(x + h) - f’(x)}{h}
  $$

2.用更好的方法求导

• 加/减法法则：

  若$f(x) = g(x) \pm h(x)$，则$f’(x) = g’(x) \pm h’(x)$

• 乘法法则：
  $$
  \frac{d}{dx}(uv) = \frac{du}{dx}v + \frac{dv}{dx}u
  $$

• 乘积法则的推广
  $$
  \frac{d}{dx}(uvw) = \frac{du}{dx}vw + \frac{dv}{dx}uw + \frac{dw}{dx}uv
  $$

• 除法法则：

  若$f(x) = \frac{g(x)}{h(x)}$，则有：
  $$
  f’(x) = \frac{g’(x)h(x) - g(x)h’(x)}{(h(x))^2}
  $$

• 链式求导法则：

  若$u$是$v$的函数，$v$是$s$的函数，则有：
  $$
  \frac{du}{ds} = \frac{du}{dv}\frac{dv}{ds}
  $$

3.三角函数的导数与极限

$\hspace{1cm}$首先有一个基本的定理（这里暂且不证）：
$$
\lim_{x \to 0} \frac{sin(x)}{x} = 1
$$
$\hspace{1cm}$然后先看一个极限：
$$
\lim_{x \to 0} \frac{cos(x) - 1}{x} = \lim_{x \to 0} \frac{cos^2(x) - 1}{x \cdot (cos(x) + 1)} = \lim_{x \to 0} \frac{-sin^2(x)}{x \cdot (cos(x) + 1)} \= \lim_{x \to 0}\frac{sin(x)}x \times (-sin(x)) \times\frac{1}{cos(x) + 1} = (1) \times (0)\times (\frac12) = 0
$$

$\hspace{1cm}$接下来求$f(x) = sin(x)$的导数：
$$
f’(x) = \lim_{h \to x} \frac{sin(x + h) - sin(x)}{h} = \lim_{h \to x} \frac{sin(x)cos(h) + cos(x)sin(h) - sin(x)}{h} \ = \lim_{h \to x} \frac{sin(x) \cdot (cos(h) - 1)}h + \lim_{h \to x}\frac{sin(h)}h \cdot cos(x) \=\lim_{h\to x}\frac{cos(x) - 1}{h} \times sin(x ) + (1)\cdot cos(x) = (0 )\times sin(x) + cos(x) \times(1) = cos(x)
$$
$\hspace{1cm}$同理，我们可以得到$f(x) = cos(x)$的导数：
$$
f’(x) = -\sin(x)
$$
$\hspace{1cm}$根据这两个公式，我们可以通过乘积法则和除法法则求出$f(x) = tan(x)，f(x) = csc(x)$,$f(x) = sec(x),f(x) = cot(x)$的导数.
$$
\frac d{dx}(tan(x)) = sec^2(x)\\frac d{dx}(sec(x)) = sec(x)tan(x)\ \frac d{dx}(csc(x)) = -csc(x)cot(x) \ \frac{d}{dx}(cot(x)) = -csc^2(x)
$$

4.关于e

$\hspace{1cm}$自然常数$e$的定义：
$$
e = \lim_{n \to \infty}(1 + \frac1n)^n
$$
$\hspace{1cm}$这样做会有一个风险，那就是这个极限不一定存在。现在我们暂且不管。

$\hspace{1cm}$对于$e$的收敛性证明，我们证一个$e \le 4$即可。即我们尝试证明：
$$
(1 + \frac1n)^n \le 4
$$
$\hspace{1cm}$即要证明：
$$
\sqrt[n]{\frac14} \leq \frac{n}{n + 1}
$$
$\hspace{1cm}$根据均值不等式，我们有
$$
\sqrt[n]{\frac14} = \sqrt[n]{\frac12 \times \frac{1}{2} \times 1^{n - 2}} \le \frac{n - 1}n \le \frac n{n + 1}
$$
$\hspace{1cm}$因此得证$e \le 4$.

​

$\hspace{1cm}$然后我们来求一个极限：
$$
\lim {n \to \infty}(1 + \frac rn)^n
$$
$\hspace{1cm}$令$k = \frac nr$，则$n = rk$，所以有：
$$
\lim {n \to \infty}(1 + \frac rn)^n = \lim{n \to \infty} (1 + \frac1k)^{rk} = \lim{n \to \infty}((1 + \frac1k)^k)^r = e^r
$$

5.对数函数和指数函数的导数

$\hspace{1cm}$先来求对数函数的导数，设$f(x) = \log_bx$，则有：
$$
f’(x) = \lim_{h \to 0} \frac{\log_b(x + h) - \log_bx} h = \lim_{h \to 0} \frac{\log_b(\frac{x + h}{x})}h = \lim_{h \to 0}\log_b(1 + \frac hx) ^ \frac1h = \lim_{h \to \infty} \log_b(1 + \frac 1h \times \frac1x )^h = \log_b e^\frac1x = \frac{1}{x \times ln(b)}
$$

$\hspace{1cm}$再来看指数函数的导数。设$y = b^x$，则$x = \log_by$，所以
$$
\frac{dx}{dy} = \frac1{y \times ln(b)}
$$
$\hspace{1cm}$则：
$$
\frac{dy}{dx} = yln(b) = b^xln(b)
$$

6.对$y = f(x)^{g(x)}$求导

$\hspace{1cm}$一个例子胜千言。比如我们现在要对$y = x^x$求导。

$\hspace{1cm}$有：
$$
ln(y) = xln(x) \ \frac d{dx} ln(y) = \frac d{dx} (x ln(x)) \ \frac d{dy}(ln(y)) \times \frac{dy}{dx} = ln(x) + 1 \ \frac1y \times \frac{dy}{dx} = ln(x) + 1 \ \frac{dy}{dx} = (ln(x) + 1) \times x^x
$$
$\hspace{1cm}$我们再举一个例子，这个例子推出的结论也是很重要的一个结论。我们现在要求$y = x^a$的导数。

$\hspace{1cm}$有：
$$
ln(y) = aln(x) \ \frac d{dx}(ln(y)) = \frac {d}{dx}(aln(x)) \ \frac d{dy}(ln(y)) \times \frac{dy}{dx} = \frac ax \ \frac{dy}{dx} = \frac ax \times y = \frac ax \times x^a = ax^{a - 1}
$$

7.指数增长和指数衰变

• 指数增长

$\hspace{1cm}$假设$y = Ae^{kx}$，则$\frac{dy}{dx} = Ake^{kx}$。这说明该函数的增长速度和函数值成正比。

$\hspace{1cm}$这很符合现实中的一些情况。一个生物种群，它扩张繁殖的速度和这个生物种群内生物的多少成正比。

$\hspace{1cm}$让我们来解决一个问题。一个兔子种群现在有1000只兔子，而3年后增长到64000只，那么4年后会有多少兔子呢？

$\hspace{1cm}$设$f(x)$表示兔子种群在第$x$年有$f(x)$只兔子，那么我们有$f(0) = 1000$,$f(3) = 64000$.

$\hspace{1cm}$根据指数增长的原则，我们设$f(x) = Ae^{kx}$,则$f(0) = Ae^0$,则$A = f(0)$.

$\hspace{1cm}$所以我们有$f(x) = f(0)e^{kx} = 1000e^{kx}$,则$f(3) = 1000e^{3k} = 64000$，所以$e^{3k} = 64$，$3k = ln(64)$，$k = \frac{ln(64)}3 = \ln(4)$，所以$f(x) = 1000e^{\ln(4)x}$。将$x = 4$代入，有$f(4) = 1000e^{\ln(4) \times 4} = 1000e ^ {\ln(256)} = 256000 $.所以4年后有256000只兔子。

$\hspace{1cm}$同时我们也可以得到，一般对于这种建模，我们都有$f(t) = f(0)e^{kt}$，

$\hspace{1cm}$可以从上述例子中看出，指数函数增长得很快。所以我们推测出一下定理（可用洛必达法则证明）：
$$
\lim_{x\to \infty} \frac{f(x)}{b^x} = 0,其中f(x)是关于x的多项式，b > 1
$$

• 指数衰减

$\hspace{1cm}$指数衰减适用于给原子衰变建模。因为原子越多，其衰变速度越快。换句话说，衰变速度与原子个数成正比。

$\hspace{1cm}$现在假设你有一瓶铀—235，它的半衰期是7年，也就是说过7年你打开这个瓶子，你会发现这个瓶子里面只有一半铀-235了。如果你初始又50公斤的铀-235，那么过10年之后你还有几公斤的铀-235没有衰变呢？

$\hspace{1cm}$设$f(t)$是时间为$t$时你剩下的铀-235，那我们应该有：
$$
f’(t) = -kf(t),其中k为常数
$$
$\hspace{1cm}$所以我们设$f(t) = Ae^{-kt}$，则$f(0) = Ae^0 = A = 50$，所以$f(t) = 50e^{-kt}$。又因为$f(7) = 50e^{-7k} = 25$，所以$-7k = ln(\frac 12) = \ln(1) - \ln(2) = -\ln(2)$，所以$k = \frac{\ln 2}7$，$f(t) = 50e^{\frac{-t \ln2}7}$。当$t = 10$时，$f(10) = 50e^{\frac{-10 \ln2}7}$。

$\hspace{1cm}$同时我们也可以得到，一般对于这种建模，我们都有$f(t) = f(0)e^{-kt}$，同时$k = \frac{\ln2}{t_{1/2}}$，其中$t_{1 / 2}$表示半衰期时间。

$\hspace{1cm}$和指数增长那一块一样，我们会得出几个有关极限的结论：

• 对数函数在$\infty$附近增长缓慢：

$$
\lim_{x \to \infty} \frac{\log_b x}{f(x)} = 0,其中f(x)是关于x的多项式,b > 1
$$

• 对数函数在$0$附近增长缓慢：
  $$
  \lim_{x \to 0}f(x)\cdot \log_bx = 0,其中f(x)是关于x的多项式,b > 1
  $$

$\hspace{1cm}$ 当$f(x) = x$时关于上面这个极限的证明：
$$
\lim_{x \to 0}x\cdot \log_bx = \lim_{x \to \infty}\frac 1x \cdot \log_b(\frac 1x) = \lim_{x \to \infty} \frac{-\log_bx}{x} = 0
$$

8.双曲函数

定义：
$$
sinh(x) = \frac{e^x - e^{-x}}2 \ cosh(x) = \frac {e^x + e^{-x}}2 \tanh(x) = \frac{sinh(x)}{cosh(x)} \ csch(x) = \frac1{sinh(x)} \ sech(x) = \frac1{cosh(x)} \ coth(x) = \frac1{tanh(x)}
$$
注意到
$$
cosh^2(x) - sinh^2(x) = 1
$$
如果对其求导，会得到：
$$
\frac d{dx}(sinh(x)) =\frac d{dx}(\frac{e^x - e^{-x}}2) = \frac{e^x + e^{-x}}2 = cosh(x)
$$

$$
\frac d{dx}(cosh(x)) =\frac d{dx}(\frac{e^x + e^{-x}}2) = \frac{e^x - e^{-x}}2 = sinh(x)
$$

这也是其前缀$sin$，$cos$的原因。

不管怎样，你可以通过链式求导或除法法则得到如下结果：
$$
\frac{d}{dx}(tanh(x)) = sech^2(x)\\frac d{dx}(sech(x)) = -sech(x)tanh(x)\ \frac d{dx}(csch(x)) = -csch(x)coth(x) \ \frac{d}{dx}(coth(x)) = -csch^2(x)
$$
注意到它们与三角函数导数之间的关系（事实上，这段公式是我从三角函数那里复制下来再轻微改造得到的）。

顺便说一句，$cosh(x)$的图像就是悬链线的图像，悬链线就是一个固定绳子的两段，在重力场中让它自然垂下，绳子的曲线方程.

9.反函数

函数本质是一个映射。一个元素$x$经过函数$f$的映射后就变成了元素$f(x)$，那么将$f(x)$变回$x$的映射就叫做函数$f$的反函数，记为$f^{-1}$,也就是$f^{-1}(f(x)) = x$。

一个函数$f$如果要有反函数$f^{-1}$，要满足对于每一个$y$，最多只有一个定义域内的$x$使得$f(x) = y$.

对于一个函数$f$，如果$f’(x)$恒大于等于0，且只有有限多个$x$使得$f’(x) = 0$，那么显然$f$存在反函数。同样的，对于一个函数$f$，如果$f’(x)$恒小于等于0，且只有有限多个$x$使得$f’(x) = 0$，那么显然$f$也存在反函数。

如果我们现在已经知道$f(x)$和$f’(x)$，如何求$f^{-1}(x)$的导数呢？

首先如果$y = f^{-1}(x)$，那么
$$
x =f(y) \ \frac{dx}{dy} = \frac{d}{dy}(f(y)) \ \frac{dx}{dy} = f’(y) \ \frac{dy}{dx} = \frac 1{f’(y)}
$$

所以我们得到了反函数的导数。

特别的，反函数的图像与原函数的图像关于$y = x$对称。

10.再谈导数

导数是一个很强大的工具，所以我们重新来挖掘一下它的潜在价值。

一阶导数$f’(x)$表现的是函数$f$的增减性。$f’(x) > 0$则函数在x上增长，$f’(x) < 0$则函数在x上减少。

二阶导数$f’’(x)$表现得是函数$f$的凹凸性。$f’’(x) > 0$则函数在x处凹面向上，$f’’(x) < 0$则函数在x处凹面向下。函数$f$的凹凸性质改变的临界点叫做函数$f$的拐点。在拐点$x$上，必定有$f’’(x) = 0$.

有一个不证自明的事实。函数$f$的最大值/最小值只会是$f(x)$，其中的$x$满足$f’(x) = 0$或$f’(x)$不存在或$x$是闭区间的端点.

现在我们的任务是求某一个函数的最值。比如说$f(x) = x^2 - 2x +2$，通过配方它有最小值1。但如果我们以导数的视角，你就会先对其求导得到$f’(x) = 2x - 2$，那么$f’(x)$的零点是1。而$f’’(x) = 2 > 0$，所以函数凹面向上，$f(1) = 1$是函数$f$的最小值。

上面这个例子不能体现处导数求极值的优越性，让我们再来看一个栗子。

求函数$f(x) = 5x \sqrt{900 - 6x}$的最大值。

对其求导，得到$f’(x) = \frac{45(100 - x)}{\sqrt{900 - 6x}}$。导数函数的零点为100。导数函数只有这一个零点，说明这一定是最大值或者最小值。让我们再看一下，对于任意的$f’(v)(v < 100)$都有$f’(v) > 0$，对于任意的$f’(w)(w > 100)$都有$f’(w) < 0$。所以$f(100) = 5000 \sqrt{3}$是函数的最大值。

11.一些定理以及推论

• 罗尔定理

  若函数$f$在闭区间$[a,b]$间连续，在开区间$(a,b)$间可导，如果$f(a) = f(b)$，则在开区间$(a,b)$中必定存在一点$c$，满足$f’(c) = 0$.

• 拉格朗日中值定理

  若函数$f$在闭区间$[a,b]$间连续，在开区间$(a,b)$间可导，则在开区间$(a,b)$中必定存在一点$c$，满足$f’(c) = \frac{f(b) - f(a)}{b - a}$。

• 拉格朗日中值定理的推论

  如果一个函数$f$的导函数$f’$对于定义域内的任意$x$满足$f’(x) = 0$，则函数$f$为常数函数。

证明：固定其定义域内一点$s$，设$f(s) = C$。再任取其定义域内一点$t$，因为导函数恒为0，所以$\frac{f(s) - f(t)}{s - t} = 0$，所以$f(s) = f(t) = C$，所以对于定义域内任意一点$t$，都有$f(t) = C$。所以函数$f$为常数函数。

12.线性化

估算$\sqrt{11}$.

这里的方法（线性化）是先将其函数化，将原问题转化为对于函数$f(x) = \sqrt{x}$，求$f(11)$.

然后我们找一个离$11$很近且很好求的$f(x)$，比如$f(9)$。求出$f’(9) = \frac 16$。我们记通过（9，3）的切线为$L$，有$L = \frac 16 x + \frac 32$，则$L(11) = \frac {10} 3$。我们估算出来的值为$\frac{10}3$.

这里我们得到近似公式：
$$
f(x) \approx L(x) = f(a) + f’(a)(x - a) 其中a是你选择的一个离x较近的且好算的值
$$
同时观察可得：

• 如果$f’’$在a和x之间为正，则通过线性化得到的估算是低估。

• 如果$f’’$在a和x之间为负，则通过线性化得到的估算是高估。

  同时我们对于误差也有一个很好的公式：
  $$
  误差 = \frac 12 f’’(c)(x - a)^2，其中c为在x和a之间的某个数。
  $$

13.牛顿法

牛顿法是用来估算函数零点（解方程）的方法。

一图胜千言

其中$x^*$是真正的零点，$x_k$是估算的点，$x_{k + 1}$是更好的估算的点。

牛顿法只在一般情况下适用。在某些特殊情况下牛顿法不适用。

14.洛必达法则

• A. $\frac0 0$或 $\frac{ \pm \infty}{\pm \infty}$形：

  对于极限$\lim_{x \to a} \frac{g(x)}{h(x)}$，如果$g(a) = h(a) = 0$或$g(a) = \pm \infty$,$h(a) = \pm \infty$，那么：

$$
\lim_{x \to a} \frac{g(x)}{h(x)} = \lim_{x \to a} \frac{g’(x)}{h’(x)}
$$

• **B. $0 \times \pm \infty$**形：

  对于极限$\lim_{x \to a} {g(x)}{h(x)}$，如果$g(a) =0,h(a) = \pm \infty$，则：
  $$
  \lim_{x \to a} {g(x)}{h(x)} = \lim_{x \to a} \frac{h(x)}{1 / g(x)}
  $$
  因为$g(a) = 0$，所以$\frac 1{g(a)} = \pm\infty$，此时可以用洛必达法则求解。

• C.$\infty - \infty$形：

  这种形式比较难处理，可以尝试同时乘以除以一个共轭根式，创造一个分母。

  求极限$\lim_{x \to \infty}(\sqrt{x + ln(x)} - \sqrt{x})$。

$$
\lim_{x \to \infty}(\sqrt{x + ln(x)} - \sqrt{x}) = \lim_{x \to \infty} \frac{\ln x}{\sqrt{x + ln(x)} + \sqrt{x}}
$$

此时分数线上下的表达式均趋向于$\infty$，可以用洛必达法则求解。

• D.$1 ^ {\pm \infty}，0^0,\infty ^ 0$形：

  这种形式最复杂。例如：
  $$
  求\lim_{x\to a}f(x)^{g(x)}
  $$
  首先我们对其取对数：
  $$
  \lim_{x\to a}\ln(f(x)^{g(x)}) = \lim_{x\to a}g(x)\ln(f(x))
  $$

  这个时候如果该式子是不定式，我们可以用$B$类型对其求极限。如果不是，你需要另外想办法。

  如果你求得了上面这个式子的极限，这时，就有：
  $$
  \lim_{x\to a}\ln(f(x)^{g(x)}) = \lim_{x\to a}g(x)\ln(f(x)) = L \ \lim _{x \to a}f(x)^{g(x)} = e^L
  $$

P6175（数学化语言表述，较严谨且易理解）

考虑一个环：$a_1- >a_2 ->a_3 ->…… ->a_n -> a_1$ $(n \ge 3)$，设$max(a_i)(1 \le i \le n) = a_k$，设$a_k$在环中相邻的两个点分别是$a_v$和$a_w$。

对于任意的几个环，如果它们的$a_k,a_v,a_w$都分别相等，我们就把这几个环都放入一个集合，并设这个集合为 $S(a_k,a_v,a_w)$。

可以发现，任意一个环都属于一个集合。

令$d(x,y)$表示$x$和$y$之间直接距离（不经过其他点）。令$f(x,y,k)$表示x和y之间经过若干个编号$<k$的点得到的最短距离。

则易证，对于任意一个集合（设这个集合为$S(a_k,a_v,a_w)$)，该集合中的最小环的长度为$d(a_v,a_k) + d(a_k,a_w) + f(a_v,a_w,a_k)$。

因为任意一个环都属于一个集合，所以我们只要枚举所有的集合，将该集合中最小环的长度作为可能的答案进行比较，即可得到最终答案。

现在还有一个问题，那就是如何求出$f(a_v,a_w,a_k)$。

我们可以发现$floyd$算法的外循环$k$枚举到$a_k$时，$a_v,a_w$之间的最短路径即为所求。

综上，时间复杂度$O(n^3)$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int maxn = 105,maxm = 1e4 + 5,inf = 0x3f3f3f3f;

int n,m,vi,vj,vk,minn;
int f[maxn][maxn],v[maxn][maxn],a[maxn][maxn];
vector<int> path;

void work(int x,int y) {
	if (v[x][y] == 0)
		return;
	int tmp = v[x][y];
	work(x,tmp);
	path.push_back(tmp);
	work(tmp,y);	
}

int main() {
	scanf("%d %d",&n,&m);
	memset(f,0x3f,sizeof(f));
	memset(a,0x3f,sizeof(a));
	for (int i=1; i<=n; i++)
		f[i][i] = a[i][i] = 0;
		
	for (int i=1; i<=m; i++) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		if (x > n || y > n)
			continue;
		a[x][y] = min(a[x][y],z);
		a[y][x] = min(a[y][x],z);
		f[x][y] = min(f[x][y],z);
		f[y][x] = min(f[y][x],z);
	} 
	
	minn = inf;
	
	for (int k=1; k<=n; k++) {
		for (int i=1; i<k; i++)
			for (int j=i + 1; j<k; j++) {
				if ((long long)a[i][k] + a[k][j] + f[i][j] < (long long)minn) {
					minn = a[i][k] + a[k][j] + f[i][j];
					path.clear();
					path.push_back(i);
					path.push_back(k);
					path.push_back(j);
					work(j,i);
				}

			}
			
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++) {
				if (i == j || j == k || i == k)
					continue;
					
				if (f[i][j] > f[i][k] + f[k][j]) {
					f[i][j] = f[i][k] + f[k][j];
					v[i][j] = k;
				}
			}
	}
		
			
	if (minn == inf) {
		puts("No solution.");
		return 0;
	}
	
	for (int i=0; i<path.size(); i++)
		printf("%d ",path[i]);
	
	return 0;
}