排列组合
最基本的：
\[\binom{n}{k}=\binom{n-1}{k-1} +\binom{n-1}{k}=\frac{n}{k}\binom{n-1}{k-1}
\]
然后是上指标求和：
\[\sum^{m}_{i=0} \binom{n+i}{n}=\binom{n+m+1}{n+1}
\]
证明考虑组合意义：
有n+m+1个黑球，最右面的黑球相当于枚举的i，也就是分界线，然后再在左面选n个黑球
等价于在总的黑球里选n+1个黑球
接下来是这两个，第二个是范德蒙德卷积：
\[\sum_{i+j=n} \binom{i}{m}\binom{i}{k}=\binom{n+1}{m+k+1}\\
\sum_{i+j=n} \binom{m}{i}\binom{k}{i}=\binom{m+k}{n}
\]
证明可以使用小球或者网格图，其中网格图的思想较为有启发意义
如下
容斥
首先是求子集版的高维前缀和
有两种复杂度的实现方式
点击查看代码
for(int i=0;i<(1<<n);i++){for(int j=i;j>=0;j=((j-1)&i)){g[i]+=f[j];}
}
点击查看代码
for(int i=0;i<=n-1;i++){for(int j=0;j<(1<<n);j++){if((j>>i)&1)f[j]+=f[j^(1<<i)];}
}
第一种 \(O(3^n)\)，优点是可以直接求单点，还有可以写数学公式
第二种 \(O(n2^n)\)，优点当然是快
然后差分就作为了逆运算
\[f_S=\sum_{T\subset S}(-1)^{|S\setminus T|} g_T
\]
还有种差分就是对于第二种前缀和方式，将加号改为减号就好了
对于一个max卷积
\[c_x=\sum_{\max(y,z)=x}a_y b_z
\]
设g为c的前缀和，有
\[g_x=(\sum_{y<=x}a_y)(\sum_{z<=x}b_z)
\]
对于一个按位或卷积
\[c_x=\sum_{y\cup z=x}a_y b_z
\]
有
\[\sum_{T\subset x}c_T=(\sum_{y\subset T}a_y)(\sum_{z\subset T}b_z)
\]
同理可得对于按位与卷积
\[c_x=\sum_{y\cap z=x}a_y b_z
\]
有
\[\sum_{T\supset x}c_T=(\sum_{y\supset T}a_y)(\sum_{z\supset T}b_z)
\]
这就是 FMT 快速莫比乌斯变换
首先正有理数可以表示为一个向量
接下来考虑一个东西
\[g_n=\sum_{d|n}f_d
\]
考虑差分
\[for \ p\in \Bbb{P}\\
for \ n
\]
\[g_{np}-=g_n;
\]
复杂度同埃氏筛 \(O(nlooglogn)\)
考虑另一种差分方式
则
\[f_n=\sum_{d|n}\mu (\frac{n}{d})g_d
\]
有个 \(\mu\)是因为n与d的向量每差一位都会有一个1的系数，且每位差距必须小于2
有 \(\mu\) 的定义
\[\mu(n) =
\begin{cases}
1 & if\ n = 1, \\
0 & if \ \exist p , p^2 \mid n\\
(-1)^k & else
\end{cases}
\]
十分完美
这就是莫比乌斯反演
接下来是二项式反演
定义
\[f_S=a_{|S|}\\g_S=\sum_{T\subset S}f_T\\
\]
显然g也只集合大小有关，与设
\[g_S=b_{|S|}
\]
则
\[b_n=\sum_{k=0}^{n} \binom {n}{k}a_k
\]
因为
\[f_S=\sum_{T\subset S}(-1)^{|S\setminus T|} g_T
\]
所以
\[a_n=\sum_{k=0}^{n} (-1)^{n-k}\binom {n}{k}b_k
\]
好了没了