min-max容斥

min-max容斥

min-max容斥

$$
max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)
$$

$$
min(S)=\sum_{T\subseteq S}(-1)^{|T|-1}max(T)
$$

杜教筛

杜教筛

杜教筛用来解决类似求$\sum_{i=1}^nf(i)$的问题

设$S(n)=\sum_{i=1}^nf(i)$

假如我们现在找到了一个积性函数$g$,那么考虑下式(其中$*$表示狄利克雷卷积)

数论中的一些常用结论

数论中的一些常用结论

$\sigma(nm)=\sum_{i|n}\sum_{j|m}\epsilon((i,j))$

证明

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

$$\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]$$

花里胡哨的二项式系数

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

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

二项式系数

$$\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}
$$

一个关于整值函数的结论

结论

设$f(x)$是任意一个具有如下性质且在一个实数区间连续的单调递增函数且

$$f(x)=整数\to x=整数 $$

只要$f(x),f(\lfloor x \rfloor), f(\lceil x \rceil)$有定义,那么就有

$$f(\lfloor x \rfloor)=\lfloor f(\lfloor x \rfloor) \rfloor 和 f(\lceil x \rceil)=\lceil f(\lceil x \rceil) \rceil$$

多项式求逆

定义

我们说$B(x)$是$A(x)$在模$x^n$意义下的逆元则是满足

$$A(x)\ast B(x)\equiv1(mod \; x^n)$$

分治

考虑分治

假如我们已经知道在模$x^{\lceil \frac{n}{2} \rceil}$下$A$的逆$B’$

FFT与NTT

快速傅立叶变换 FFT

对于两个多项式

$$A(x)=\sum_{i=0}^{N-1}a_ix^i$$

$$B(x)=\sum_{i=0}^{N-1}b_ix^i$$

FFT可以在$O(nlgn)$的时间内求出

$$C(x)=A(x)*B(x)=\sum_{i=0}^{2(N-1)}c_ix^i$$

其中$c_i=\sum_{j=0}^ia_jb_{i-j}$

Your browser is out-of-date!

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

×