数学

斐波那契

\[gcd(F_i,F_j)=F_{gcd(i,j)}\\ \sum_{i-1}^nF_i=F_{n+2}-F_2 \]

二项式反演

定义 \(g(m)\) 表示恰好选 \(m\) 个时的方案数，\(f(m)\) 必定选\(m\) 个，其余不管的方案数。

由于 \(g\) 往往需要满足其余的数不选，所以会不是很好算，而 \(f\) 确是好算的，那么有以下公式：

\[f(k)=\sum_{i=k}^n C_{i}^{k} g(i)\\ g(k)=\sum_{i=k}^n (-1)^{i-k}C_{i}^kf(k) \]

那么求完 \(f\) 就可以 \(NTT\) 了。

例题

P4491 [HAOI2018] 染色

FWT

FWT 的思想就是将数列经过变换后，将位运算卷积变为逐位相乘，最终通过逆变换将其得到所求数列。单次 FWT 的时间复杂度为 \(O(2^nn)\) 可以将 \(O(3^n)\) 甚至更高的卷积优化。

或卷积

有 \(C_s=\sum_{s=t|z}A_t\times B_z\) ，\(FWT(F)_s=\sum_{t \subseteq s}F_t\)。

可以发现 \(FWT\) 的变换就是求每个集合的子集和，这个东西是容易用高维前缀和做到 \(O(2^nn)\)。下面将证明它的正确性：

\[FWT(C)_s=FWT(A)_s \times FWT(B)_s \\ \sum_{w\subseteq s}C_s=\sum_{x\subseteq s}A_x \sum_{y\subseteq s}B_y\\ \sum_{w\subseteq s} \sum_{w=x|y} A_x\times B_y=\sum_{x\subseteq s}A_x \sum_{y\subseteq s}B_y \]

发现两边意义相同，证毕。

由于其良好的性质，计算单值时可以做到 \(O(2^n)\) ，简单容斥即可。

与卷积

和或卷积几乎同理。

异或卷积

有 \(C_s=\sum_{s=t\oplus z}A_t\times B_z\) ，\(FWT(F)_s=\sum_{t\circ s=0}F_t-\sum_{t\circ s=1}F_t\)。

(定义\(s\circ t=popcount(s\&t)(mod\ 2)\))

变换本身是容易的，直接依次考虑 \(2^i\) 的贡献即可，证明如下：

\[FWT(C)_s=FWT(A)_s\times FWT(B)_s\\ \sum_{t\circ s=0}C_t-\sum_{t\circ s=1}C_t=(\sum_{x\circ s=0}A_t-\sum_{x\circ s=1}A_t)(\sum_{y\circ s=0}B_t-\sum_{y\circ s=1}B_t)\\ \sum_{t\circ s=0}\sum_{x\oplus y=t}A_xB_y-\sum_{t\circ s=1}\sum_{x\oplus y=t}A_xB_y= (\sum_{x\circ s=0}A_t\sum_{y\circ s=0}B_t+ \sum_{x\circ s=1}A_t\sum_{y\circ s=1}B_t)- (\sum_{x\circ s=0}A_t\sum_{y\circ s=1}B_t+ \sum_{x\circ s=1}A_t\sum_{y\circ s=0}B_t) \]

注意到有 \((x\oplus y)\circ s=(x\circ s)\oplus (y\circ s)\)，所以式子左右两边相等。

子集卷积

子集卷积一般使用或卷积实现，在或卷积的基础上，再加上位数的限制就行了。时间复杂度会多一个 \(n\)。

杂谈

乘法转化

将乘法转化成加和，可做卷积。

\[ab=C_{a+b}^2-C_a^2-C_b^2 \]

组合恒等式

\[\sum _{i=x}^n C_i^x=C_{n+1}^{x+1} \]

Min-Max容斥

\[max(A)=\sum_{T\subseteq A} min(T) (-1)^{|T|+1} \]

组合意义

有 \(n\) 个小球，\(a\) 个白球，\(b\) 个黑球，有若干种排列方式，现在记在所有排列方式中黑球的下标和为 \(d\)。问加入一个白球后，所有排列方式中黑球的下标和。

首先，有 \(n+1\) 中加的方式，所以继承下来，有 \((n+1)d\)

令黑球的位置集合为 \(P\) ，\(p_0=0,p_{b+1}=n+1\) ，考虑当前加入的白球后有多少个黑球贡献加一：

\[\sum_{i=1}^{b+1}(p_i-p_{i-1})(b-i+1)\\ =\sum_{i=1}^bp_i\\ =d \]

所以当前的答案是 \((n+2)d\) 。

若是加入黑球就在此基础上加上这个黑球的贡献。

匹配数

从 \(n\) 个数中选取 \(\frac n2\) 对数，方案有 \(w(n)=1\times 3\times 5\times...\times (n-1)\)，当 \(n\) 为奇数时为 \(0\)。