数论中的一些常用结论

最重要的十个二项式系数恒等式

$$\binom{n}{k}=\frac{n!}{k!(n-k)!},整数n\geq k\geq 0$$ 阶乘展开式
$$\binom{n}{k}=\binom{n}{n-k},整数n\geq 0,k是整数 $$ 对称恒等式
$$\binom{r}{k}=\frac{r}{k}\binom{r-1}{k-1},整数k\neq 0$$ 吸收/提取恒等式
$$\binom{r}{k}=\binom{r - 1}{k}+\binom{r - 1}{k - 1},k是整数 $$ 加法/归纳恒等式
$$\binom{r}{k}=(-1)^k\binom{k-r-1}{k},k是整数 $$ 上指标反转
$$\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k} ,m,k是整数 $$ 三项式版恒等式
$$\sum_k\binom{r}{k}x^ky^{r-k}=(x+y)^r,整数r\geq 0 或者 \vert x/y \vert <1 $$ 二项式定理
$$\sum_{k\leq n}\binom{r+k}{k}=\binom{r+n+1}{n},n是整数 $$ 平行求和法
$$\sum_{0\leq k \leq n}\binom{k}{m}=\binom{n+1}{m+1},整数m,n\geq 0 $$ 上指标求和法
$$\sum_{k}\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n},n是整数 $$ 范德蒙德卷积公式

微积分

常用的导数

$$(C)’=0$$

$$(x^{\mu})’=\mu x^{\mu - 1}$$

$$(\sin x)’=\cos x$$

$$(\cos x)’=-\sin x$$

$$(\tan x)’=\sec ^2 x$$

$$(a^x)’=a^x \ln a$$

$$(e^x)’=e^x$$

$$(\log_a x)’=\frac{1}{x ln a}$$

$$(\ln x)’=\frac{1}{x}$$

反演

反演的本质

对于可逆下三角矩阵$A$(可以归纳证明$A^{-1}$也是下三角矩阵),有$f=Ag$,那么$g=A^{-1}f$

即:

$$f_i=\sum_{j=0}^ia_{ij}g_j\Rightarrow g_i=\sum_{j=0}^ib_{ij}f_j$$

其中:
$$\sum_{k=0}^na_{ik}b_{kj}=[i==j]$$

64位模数乘法

当模数是一个64位的整数时,乘法取模过程中就会溢出。

此时有两种解决方法

一种是采取与快速幂类似的思想,时间复杂度位$O(lg)$

边分治

边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树,合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树,就可以很好地解决问题。

CDQ分治与点分治的碰撞

看到了[Noi2014]购票这道题目,发现了这种操作(为什么之前没想到呢。。。)

代码还没写过,先口胡一下

有根树上的DP,每个点只能从祖先转移。

密码Hello

Hello

更新主题

今天突然发现icarus主题不知道什么时候更新了

搞了一会儿更新好了,感觉好看了不少

前后对比图:

花里胡哨的二项式系数

跳进了这个坑。。。于是就开始自闭了。

还有许许多多关于二项式系数的东西没有写,以后会补的(?)

二项式系数

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

严格一点的定义:

$$
\binom{n}{m}=\begin{cases}
\frac{n!}{m!(n-m)!} & 整数m\geq 0\
0 & 整数m<0
\end{cases}
$$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×