# 数学（除数论） ## 手工加减进退位 - 核心是两个数组，`digit[MAXN]`和`carry[MAXN]`，其中digit只存该位模10后的结果，carry存该位应有的进位数（也就是第i位溢出会记录在第i+1位的carry中）。 - 对加减法，carry和digit可以线性进行一遍，一边更新下一位的carry一边更新这一位的digit - 对乘法，手工竖式阶段先让digit存该位的完整值，即不进位，然后再从低位到高位按加法方式线性更新digit和carry ## 快速幂/矩阵快速幂 poj 3070 hdu 6030 hdu 5564 快速幂就是用“底数相同，指数相加”的思路二进制分解一个幂次，如 $x^{11}=x^8x^2x^1$ 对应为二进制 $11_{(10)}=1011_{(2)}$。时间复杂度 $O(\log_2n)$，实际是倍增法的思想。 矩阵快速幂也就是把一个齐次线性递推关系的加法和乘法变成向量运算，为了形成方阵再补几个自由变量，如： $$ \begin{aligned} f(n)&=f(n-1)-3f(n-2) \\ \begin{pmatrix}f(n)\\ f(n-1)\end{pmatrix} &= \begin{pmatrix}1&-3\\ 1&0\end{pmatrix} \begin{pmatrix}f(n-1)\\ f(n-2)\end{pmatrix} \\ &= \begin{pmatrix}1&-3\\ 1&0\end{pmatrix}^2 \begin{pmatrix}f(n-2)\\ f(n-3)\end{pmatrix} \\ &\;\;\vdots\\ &= \begin{pmatrix}1&-3\\ 1&0\end{pmatrix}^{n-2} \begin{pmatrix}f(2)\\ f(1)\end{pmatrix} \end{aligned} $$ ```cpp int qpow_mod(int x, int p, int m) { int res = 1; int base = x; while(p) { if (p & 1) res = res * base % m; p >>= 1; base = base * base % m; } return res; } ``` ## 进制转换/多进制状压 进制转换： - k转10：低位开始，先乘指数后加，下一位指数+1 - 10转k：低位开始，先模k再赋值，下一位除以k 多进制状压： - 核心思想：用函数封装数位操作 - 取位：对k进制数x，取第n位为：`(x/(k^n)) % k`，n从0开始 - 左移n位：`x *= k^n` - 右移n位：`x /= k^n` - 最低(非)0位：没有二进制的简便方法，只能不断右移 - `k^n`可以打表 ## 逆序对 归并排序的归并过程中，每一次选右时，还没选过的左元素都与该右元素形成一次逆序。 ## 组合数学 - 组合数/排列数 - P(n, m)是从n递减乘m个 - C(n, m)是从n递减乘m个，再除以m的阶乘 - 容斥 - 对重复的集合，先加单元素集合再减双元素集合再加三元素集合，一直到全集。 - 二项式反演 - 对于形如$g(k)=\sum_{i=k}^n{\tbinom{i}{k}f(i)}$的组合求和情况，其反演为$f(k)=\sum_{i=k}^n{(-1)^{i-k}\tbinom{i}{k}g(i)}$ - 例：至少和恰好的二项式反演 - 在$n$个有区分模式中恰好存在$k$个特定模式的可能情况数记为$f(k)$ - 在$n$个有区分模式中至少存在$k$个特定模式的可能情况数记为$g(k)$ - $g(k)=\sum_{i=k}^n{\tbinom{i}{k}f(i)}$ - $f(k)=\sum_{i=k}^n{(-1)^{i-k}\tbinom{i}{k}g(i)}$ - （补充）至多和恰好的差分反演 - 在$n$个有区分模式中至多存在$k$个特定模式的可能情况数记为$h(k)$ - $h(k)=\sum_{i=0}^k{f(i)}$ - $f(k)=h(k)-h(k-1)$ - 卡特兰数 - 若有两种不同事件各可选择n次，一种事件的发生个数在一个时刻必须比另一个多或者恰好相等，则这样的排列数构成卡特兰数 -  -  -  - x 斯特林数 ## 母函数 各种独立事件的可能选择的母函数乘起来，x的系数就是加起来的，x^n的系数代表了共发生n个事件选择时的情况数。编程时可以找到这个乘积，直接用多项式乘法手写，也可以进一步推导。 多项式乘法直接计算： 推导通项解析式： -  -  - 记住$\sum_{i\ge0}x^n=\frac1{1-x}$，如果只需要前k项（含1）就是这个再减去$\sum_{i\ge k}x^i=\frac{x^{k}}{1-x}$ ## 博弈论 公平组合游戏：局面没有角色信息，且局面逐渐收敛 - N/P位置 - P（Previous）位置：必输位置（前一玩家必赢） - N（Next）位置：必赢位置（当前玩家必赢） - 从0状态开始推，每个状态在下一步都可达之前的状态，因此每个状态都可以推出是P位置或N位置，找规律或按动态规划求解 - 一个状态只可达N位置，则该位置为P位置（因为对手会到达N位置） - 一个状态只可达P位置，则该位置为N位置（同上） - 一个状态N和P都可达，则该位置为N位置（因为取最优决策会让对手到达P位置） - 尼姆游戏 - 从n个放置了不同个数$a_1\cdots a_n$物品的堆中，每个玩家每次可以从一个堆拿走某些数量的物品，最后没有物品可拿的输 - 解法：$res=\displaystyle\bigoplus_{i=1}^n a_i$，如果 $res=0$ 则先手输，$res\ne0$ 则先手赢 - 如果先手赢（$res\ne0$），求第一步可行的方案数： - 对第$i$堆，如果$res\oplus a_i<a_i$，意味着$res$完全没有受$a_i$的影响时，可以通过将$a_i$减小到该结果来使得新的$res=0$即让对手必输 - 统计满足上述条件的堆的个数 - SG（Sprague-Grundy）函数 - 将公平组合游戏放到DAG上，每个节点的出边为其所有后继状态 - 定义局面节点$u$的SG函数为： - $\displaystyle SG(u)=\min_{x\in \mathbb{N}\setminus\{SG(v);\ u\rightarrow v\}}x$ - 就是除去当前节点的后继节点的所有SG值后，最小的自然数（含$0$） - 如后继节点SG为$\{0,1,4\}$则当前节点为$2$，后继节点为$\{1,2,3,4\}$则当前节点为$0$。 - 终结必败局面没有出边（即不能行动），$SG=0$ - 直连任意必败节点的是必胜节点，$SG\ne0$ - 只直连必胜节点的是必败节点，$SG=0$ - 对于局面可分的游戏 $G=G_1+G_2+\cdots+G_n$，其可表示为多个DAG分量组成的非连通图，局面$(u_1,u_2,\cdots,u_n)$的SG函数为： - $SG(u_1,u_2,\cdots,u_n)=\displaystyle\bigoplus_{i=1}^n SG(u_i)$ - 显然可以用来解尼姆游戏 ```cpp int n, SG[MAXN]; void getSG(vector<int> choices) { for(int i = 1; i <= n; i++) { int next[MAXN] = {0}; for(int ch : choices) { if (i - ch < 0) continue; next[SG[i - ch]] = 1; } for(int j = 0; j < MAXN; j++) { if (!next[j]) { SG[i] = j; break; } } } } ``` - 威佐夫游戏 - 有两堆，每次可以①从一堆取任意数量②从两堆取任意相同数量 - 在黄金分割数乘以两堆数量差值恰好等于较少一堆的数量时，先手必输，否则先手必胜。 ```cpp gold=(1.0+sqrt(5))/2; x=min(a,b),y=max(a,b); return (int)(gold*(y-x)+0.5) == x; ``` ## 倍增和ST表 倍增是一种通过将一个数字拆解为2的各个幂次之和来使时间复杂度从线性降至log级别的技巧，如$11(10)=1011(2)$，即$11=2^3+2^1+2^0$。不妨将10进制数$a$的2的幂升序序列记为$B(a)$，$a=\sum_{i\in B(a)}2^i$，如对$B(11)=(0,1,3)$ - 倍增解决树上节点k级祖先问题 - 令$f(x,k)$表示节点x的k级祖先，$F(x,j)$表示节点x的$2^j$级祖先 - $F(x,0)=f(x,1)$ - $F(x,j)=F(F(x,j-1),j-1)$ - $f(x,k)=F(\cdots F(x,B(k)_{|B(k)|})\cdots,B(k)_1)$，如$f(x,11)=F(F(F(x,3),1),0)$。 - 倍增解决树上LCA问题 - 求解节点x和y的LCA，首先考虑x和y的深度 - 由线性遍历可得每个节点$i$的深度$D(i)$，不妨设$D(x)\le D(y)$，我们的目标是让$D(x)=D(y)$ - 考虑使用上面找k级祖先的思路，将x跳至$x'=f(x,D(x)-D(y))$ - 此时若$x'=y$，则已经找到x和y的LCA，否则进入下面的流程 - $D(x')=D(y)$且$x'\ne y$时，我们依然采用刚才$F$函数的递推思路 - 对于任意的$j$，若$F(x',j)=F(y,j)$则意味着有可能跳得太靠上，超过或等于了LCA。我们保守考虑，从大到小遍历$j$，直到找到第一个： - $x^{(1)}=F(x',j^{(1)})\ne F(y,j^{(1)})=y^{(1)}$ - 在$x^{(1)}$和$y^{(1)}$上重复找$j$的过程，直到得到 - $x^{(\theta)}=F(x^{(\theta-1)}, j^{(\theta)})\ne F(y^{(\theta-1)}, j^{(\theta)})=y^{(\theta)}$ - 此时$[0,j^{(\theta)})$中再也没有符合条件的$j$可取 - 最终有$f(x^{(\theta)},1)=f(y^{(\theta)},1)=LCA(x,y)$ ```cpp // 假设节点编号按升序排列，即fa[x]<x，可以使用DFS序 // 否则需要重新考虑init()中的递推关系 int n, fa[MAXN], F[MAXN][MAX_POW+1], dep[MAXN]; void init(){ for (int i = 1; i <= n; i++) { F[i][0] = fa[i]; for (int j = 1; j <= MAX_POW; j++) if (F[i][j-1]>0 && F[F[i][j-1]][j-1]>0) F[i][j] = F[F[i][j-1]][j-1]; } } int f(int x, int n){ for (int j = MAX_POW; j >= 0; j--) if(n - (1<<j) < 0) continue; x = F[x][j]; n -= (1<<j); return x; } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); if (dep[x] > dep[y]) x = f(x, dep[x] - dep[y]); if (x == y) return x; for(int j = MAX_POW; j >= 0; j--) { int tx = F[x][j], ty = F[y][j]; if(tx == ty) continue; x = tx; y = ty; } return fa[x]; } ``` - 倍增解决可重复贡献值问题 - 所谓可重复贡献值，是指两个有交集的集合上分别计算出的值的聚合，与二者并集直接计算出的值相等。 - 例如：GCD；区间最值(Range Max/Min)。 - **ST表**（Sparse Table） - 对于一个$[a,b)$定义域上，$[l,r)$($a\le l,r \le b$)区间上可重复贡献值的若干次查询问题，考虑预先计算$[a,b)$区间上以每个数$x$开始，长度为2的$j$次幂的区间$[x, x+2^j)$上的局部值$ST(x,j)$，即： - $ST(x,0)=V(x,x)$，$V$为该值的计算方式 - $ST(x,j)=V(ST(x,j-1),ST(x+2^{j-1},j-1)$ -  - 显然一定有且仅有一个整数$s$，使$[l,l+2^s)\cup[r-2^s,r)=[l,r)$ - 不等式形式为 $\begin{cases}l+2^s\le r\\ r-2^s\ge l \end{cases}$ - 另一不等式形式为 $2^s\le r-l\lt 2^{s+1}$ - 等式形��为 $s=\lceil\log_2 {(r-l)}\rceil$ -  - 最终答案 $V(l,r)=V(ST(l,s), ST(r-2^s,s))$ ```cpp int n, a[MAXN], ST[MAXN][MAX_POW+1]; int V(int x, int y) { return max(x, y); } void initST(){ memset(ST, 0, sizeof(ST)); for (int i = 0; i < n; i++) { ST[i][0] = V(a[i], a[i]); } for (int j = 1; j < MAX_POW; ++j) { int spli = (1 << (j-1)); for (int i = 0; i+spli < n; ++i) { ST[i][j] = V(ST[i][j-1], ST[i+spli][j-1]); } } } int query(int l, int r) { int s = floor(log2(r-l+1)); return V(ST[l][s], ST[r-(1<<s)+1][s]); } ``` ## 其它 - x 康托展开快速判重