星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

玄学算法/精彩DS总结 Vazuku

posted on 2018-10-31 11:36:51 | under Summary |

$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]$ 。

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)$ 。
至此,我们成功地筛出了这个积性函数。

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$ 学一种数据结构,于是这里暂且不提。