玄学算法/精彩DS总结 Vazuku
teafrogsf
2018-10-31 11:36:51
## $39.Difference\ Constraints$
差分约束系统是一组长成这样的不等式：
$$x_i-x_j\ge k$$
然后如果是$x_i-x_j\le k$的话，可以变成$x_i-x_j\ge -k$；$x_i-x_j=k$的话，变成$x_i-x_j\le k,x_i-x_j\ge k$就可以了。
那么怎么求解呢？
注意到$x_i\ge x_j+k$，那么我们建一条$j\to i$，权值为$k$的边。
然后我们弄一个源点$S$，对每个点满足$x_i-x_S\ge-inf,x_S=0$。
那么从源点直接跑最短路就可以了。
显然这和最短路的松弛操作是一样的。
## $Ex.Constant\ Coefficient$
## $Homogeneous\ Linear\ Recursion$
~~这名字是真的长~~
$Bonus:$在写完之前一直会存在这里占坑，写完后就搬到$slide$里去啦。
常系数齐次线性递推，指的是一类这样的递推：
$$f[n]=\sum_{i=1}^kg[i]f[n-i]$$
其中$g[i]$是一个给定的系数~~或者是DP等操作的结果~~。
然后正常情况下$k\le 500$，可以用矩乘通过。但是有那么一些丧病出题人把$k$出到$5000$甚至$50000$，从而让~~原本十多行的代码变成了一百多行~~这个线性代数魔法有了用武之地。
本篇博客各种意义上借鉴了$shadowice1984$的题解。
### 1.转化问题
首先，我们先考虑一下，对于矩阵转移的方法来说，哪些东西是我们不需要的。
### 2.构造算法
### 3.使用科技
### 4.小心实践
### 5.然后让出题人遭受血光之灾
## $40.Linear\ Sieve$
在实用性上来看，线性筛的综合性能十分优秀，也能足够应付一般的求积性函数的问题。有一个很重要的性质是**任何一个数都会被它的最小质因子筛掉。**
这个证明比较清新，就是考虑当$i\%prime[j]=0$时，$i\times prime[j+1]$会被$x\times prime[j]$筛掉，其中$x$是一个比$i$大的数，因为$i$是$prime[j]$的倍数，那么$i\times prime[j+1]$中一定有$prime[j]$。
```cpp
void sieve(int n)
{
isnprime[1]=1;
f(i,2,n)
{
if(!isnprime[i])prime[++prime[0]]=i;
for(register int j=1;j<=prime[0]&&i*prime[j]<=n;++j)
{
isnprime[i*prime[j]]=1;
if(!(i%prime[j]))break;
}
}
}
```
实际上，对于任意积性函数我们都有一种套路的筛法。
首先我们需要知道这个函数$f$的一些东西，也就是$f(1),f(p),f(p^k)$。
然后我们考虑在线性筛中我们究竟干了什么：
对于一个质数，我们单独判断。
对于两个数$i,prime_j$（显然$prime_j\le i$），当它们互质的时候我们直接让$f_{i\times prime_j}=f_i\times f_{prime_j}$，这符合积性函数的定义。
当它们不互质的时候，那么$prime_j$是$i$的第一个质因子。我们考虑记一个$lpow_i$表示$i$的最小质因子的最高次幂，譬如$63=3^2\times7$，则$lpow_{63}=9$。
也就是说$(\frac{i}{lpow_i},lpow_i\times prime_j)=1$，则$f_{i\times prime_j}=f_\frac{i}{lpow_i}\times f_{lpow_i\times prime_j}$。
所以我们只需要知道$f_{lpow_i\times prime_j}$就可以了，这个东西$\le i\times prime_j$，而当$=$即$i=lpow_i$的时候，就是我们单独定义的$f(p^k)$。
至此，我们成功地筛出了这个积性函数。
```cpp
void sieve(int n)
{
isnprime[1]=1;
f[1]=sth;//lpow[1]貌似是不需要定义的
f(i,2,n)
{
if(!isnprime[i])lpow[i]=i,prime[++prime[0]]=i,f[i]=sth;
for(register int j=1;j<=prime[0]&&i*prime[j]<=n;++j)
{
isnprime[i*prime[j]]=1;
if(!(i%prime[j]))
{
if(i^lpow[i])f[i*prime[j]]=f[i/lpow[i]]*f[lpow[i]*prime[j]];
else f[i*prime[j]]=sth;
lpow[i*prime[j]]=lpow[i]*prime[j];
break;
}
f[i*prime[j]]=f[i]*f[prime[j]];
lpow[i*prime[j]]=prime[j];
}
}
}
```
其中sth是需要预处理的内容。
## $41.Optimized\ Edge-Construction\ of\ Segment\ Tree$
线段树优化建边~~只要你能看到一个正常的介绍~~是一个非常直观的东西。
实际上也很简单，当$u\to[l,r]$连边时，建一棵自上向下连边的线段树，当$[l,r]\to u$连边时，建一棵自下向上连边的线段树，就可以只对$\log$个点连边了。
~~我真不知道有什么好写的啊~~
## $42.Extended\ Euclid$
求方程$ax+by=(a,b)$的一定情况下的整数解。
核心式子是$(a,b)=(b,a\bmod b)$。
首先当$b=0$时，$x=1,y=0$；
然后考虑我们已知一个$bx+(a\bmod b)y=(a,b)$的解$(x_0,y_0)$。
那么
$$ax+by=bx_0+(a\bmod b)y_0$$
$$=bx_0+(a-a/b\times b)y_0$$
$$=ay_0+bx_0-a/b\times by_0$$
$$=ay_0+b (x_0-a/by_0)$$
则
$$x=y_0,y=x_0-a/b\times y_0$$
在实现上，我们进入一层递归把$x,y$交换，这样$y-=a/b\times x$就可以了。
如果求出来的解不满足题目要求怎么办？$x=x\pm kb,y=y\mp ka,k\in \mathbb{Z}$就可以了。
如果题目求的是$ax+by=c,(a,b)\vert c$怎么办？
把上述求出来的$x,y\times c$就可以了。
## $43.BIT$
区间修改区间查询：
$$d_i=a_i-a_{i-1}$$
$$a_n=\sum_{i=1}^nd_i$$
$$\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^id_j$$
$$=\sum_{i=1}^n(n-i+1)d_i$$
$$=(n+1)\sum_{i=1}^nd_i-\sum_{i=1}^nid_i$$
拆成两个差分数组维护就可以了。
## $44.Asymmertic\ Game\ Theory$
## $45.Matrix+Size-Subdivision$
这里是一种时间复杂度为$O(k^3(n+m)\log^2 n)$解决一类树上DDP的算法。~~或者你也可以叫它基于变换合并的树上动态DP的链分治算法。~~
具体来说，首先我们可以发现，对于一个点权值的修改，它对树上DP值的变化仅限于它的祖先部分。
### $1.$树形随机
那么我们有一个显然的暴力是，我们对每次修改直接暴跳父亲的答案就可以了。~~这样如果树是随机的话复杂度就是期望$O(m\log n)$啦~~
显然正常情况下树不会是这样子的。
### $2.$累和$DP$
然后如果我们的DP是这个样子的：
$$dp_u=\sum dp_v$$
那么修改可以用树剖+线段树，当然因为这是链上修改、单点查询，它可以变成单点修改，子树查询，复杂度是$O(m\log n)$的。显然这也不是这个专题的内容。
### $3.$复合运算
于是这个DP会更难一点，它可能对于每一个点不止一个运算。
比如没有上司的舞会大概是这样:
$$dp[u][0]=\sum_v\max(dp[v][0],dp[v][1])$$
$$dp[u][1]=\sum_v dp[v][0]$$
显然由于有取$\max$操作，我们上面的维护方式已经无法进行。
我们联想一下：跳到根，而且要具有$O(\log)$这样的复杂度——可以发现重链剖分就有这样的性质。
也就是说，我们只要找到一种维护方法，使得对于剖分后的每条重链中的信息能够快速维护的话，就可以解决这类问题。
然后你想破脑袋觉得这个东西线段树非常难维护。
**但是神奇的猫发现**，如果对于每条重链只进行单点修改的话还是能够接受区间查询的。
那我们可以想到维护一个$g[u][0/1]$表示对于当前这个点**不包含重儿子的系数和**。
但是我们又发现一个问题：区间信息是什么呢？
然后你想破脑袋觉得这个东西线段树非常难维护。
**但是神奇的猫发现**，$\max,+$可以代替矩阵乘法中的$+,\times $，并且同样具有结合律。
那么我们可以把转移设成这样的形式：
$$\begin{bmatrix}g[v][0] & g[v][0] \\ g[v][1] & 0\end{bmatrix}\begin{bmatrix}dp[v][0] \\ dp[v][1]\end{bmatrix}=\begin{bmatrix}dp[u][0] \\ dp[u][1]\end{bmatrix}$$
然后由于叶子节点的$g=dp$，其实
$$\prod_{i=leaf}^u\begin{bmatrix}g[i][0] & g[i][0] \\ g[i][1] & 0\end{bmatrix}=\begin{bmatrix}dp[u][0] & dp[u][0] \\ dp[u][1] & 0\end{bmatrix}$$
那么我们在修改一个点的时候，对于这个点我们跳重链的时候每条重链只要修改重链底端的那个点（显然其它点不需要修改），查询直接查题目要求那个节点的重链乘积就可以了。这样的复杂度是$O(k^3(n+m)\log^2 n)$的。常数比较大，但勉强可以接受。
### $4.$辣鸡毒题
此外对于这样的DP还有一种利用$O(m\log n)$的$LCT/$全局平衡二叉树的做法，但由于$LCT$常数大，也没有必要去为了$DDP$学一种数据结构，于是这里暂且不提。