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))$

证明

常用的导数

$$(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

对于两个多项式

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