玄学算法/精彩DS总结 Vaiz

· · 个人记录

21.Bit\ DP

（摘自zjBrave_shadow博客）
套路：

我们常常是要求\len的有多少个满足要求的数。

这个限制有些恶心，我们需要多一位来看是否被限制。

我们一般按位考虑，令dp[i][0/1]为到从高到低考虑到第i位，当前有/没被n限制。

我们考虑把n按位拆下来，变成一个数组lim[i]，然后取出n的位数Bit。 每次考虑后一位放什么数字就行了。具体实现如下（用刷表法方便转移）：

dp[0][0] = 1;
for (int i = 0; i < Bit; ++ i)
    for (int now = 0; now <= 1; ++ now)
      for (int dig = 0; dig <= 9; ++ dig) if (now || (dig <= lim[i + 1]))
          dp[i + 1][now || (dig < lim[i + 1])] += dp[i][now];//这里是<的原因是，

然后最后的答案就是

ans = dp[Bit][0] + dp[Bit][1];

不难发现这样写，每个位数的数都会被考虑到。因为我们枚举的时候允许了前缀0 的存在。
并且如果存在前缀0那么后面的所有数都不会存在限制了，可以随便填。
但是注意这样的话，全部为0的也会考虑进去，我们平常要考虑是否-1就行了。

22.Convex\ Optimization

凸优化是APIO2018的讲课内容，预计将来的一段时间内会成为神仙难度的热点。详情可以见我的slide。

23.Constant\ Optimization

1.在开O2的时候，循环语句在只有一句话的时候非常快，我们可以将原本的多个语句通过预处理等形式让语句只有一句，可以大大提高循环效率。
2.你可以通过计算

unsigned long long

爆了多少次，再在最后减回来。
3.(与4一起摘自__debug博客)

std::string procStatus()
{
    std::ifstream t("/proc/self/status");
    return std::string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
//Beng哥改良版
string procStatus()
{
    freopen("/proc/self/status","r",stdin);
    string str,tmp;
    while(getline(cin,tmp))str+=tmp+'\n';
    fclose(stdin);
    return str;
}

输出它，VmPeak是内存。
4.性能分析(卡常利器)
首先在编译时加入 -pg 选项, 然后运行该程序. 程序会跑得很慢, 同时目录下会产生一个 gmon.out. 等程序跑完了之后, 运行命令 gprof program_name > result.txt. 现在 result.txt 中包含了每个函数详尽的调用次数/时间/占总时间百分比等, 是不可多得的卡常利器.

最重要的一点, 比赛时也可以用.
5.

-fsanitize=address -fsanitize=undefined

后一个用来确认是否爆int/long\ long，前一个用来确认是否爆数组。
在\rm NOI\ Linux中，后一个要用

-ftrapv

代替。

24.Tree\ DP

树上DP如果与距离相关，有一个比较好的想法/套路：
考虑按照每个点统计的子树内各个距离的DP值来转移，边转移边统计答案可以考虑好所有子树内的情况，只要这样转移到根就可以统计好所有的情况了，不需要考虑祖先。

25.EXtended\ China\ Remainder\ Theorem

扩展中国剩余定理适用于任意模数下的CRT。
我们只考虑两个式子的合并：

x\equiv a_1\pmod{m_1} x\equiv a_2\pmod{m_2}

我们先改变一下形式，变成

x-m_1k_1=a_1 x-m_2k_2=a_2

然后两式合在一起

m_1k_1+a_1=m_2k_2+a_2

同除C=(m1,m2)

\frac{m_1k_1}{C}+\frac{a_1}{C}=\frac{m_2k_2}{C}+\frac{a_2}{C}

移项

\frac{m_1k_1}{C}=\frac{m_2k_2}{C}+\frac{a_2-a_1}{C} \frac{m_1k_1}{C}\equiv\frac{a_2-a_1}{C}\pmod{\frac{m_2}{C}} k_1=inv(\frac{m_1}C,\frac{m_2}C)\frac{a_2-a_1}{C}+w\frac{m_2}{C} x_1=m_1(inv(\frac{m_1}C,\frac{m_2}C)\frac{a_2-a_1}{C}+w\frac{m_2}{C})+a_1 x_1=inv(\frac{m_1}C,\frac{m_2}C)\frac{a_2-a_1}{C}m_1+w\frac{m_1m_2}{C}+a_1 x_1\equiv inv(\frac{m_1}C,\frac{m_2}C)\frac{a_2-a_1}{C}m_1+a_1\pmod{\frac{m_1m_2}{C}} M=\frac{m_1m_2}{C} A=inv(\frac{m_1}C,\frac{m_2}C)\frac{a_2-a_1}{C}m_1+a_1

新的a_i=A,m_i=M。在实现上，乘法部分采用快速乘，\times m_1的地方\% M就可以了。M=m1/c\times m2可以避免一部分危险，因为M模不了。m_1左边的部分似乎可以\%\frac{m_2}C。
似乎除C是为了控制模数大小。

MA

26.EXtended\ Lucas\ Theorem

首先卢卡斯定理不是没用了，它更多地是把一个数化为p进制去进行解题。
扩展卢卡斯主要用来解决mod为合数的组合数运算。
我们让mod=p_1^{k_1}\cdots p_n^{k_n}，再对每个分解的质因数次幂求一遍组合数，最后用CRT合并。但我不太会普通\sout{CRT}，我就用扩展\sout{CRT}了吧。
然后我们可以用一些操作来求\binom nm\pmod{p_i^{k_i}}。
对于一个阶乘n!，我们分为三部分：p_i的倍数，这部分我们每个都除以p_i,然后就可以变为一个p_i^{\lfloor\frac n{p_i}\rfloor}还有一个\lfloor\frac n{p_i}\rfloor!；剩下的大部分数与小于p_i^{k_i}的部分乘积，以这个部分的个数为循环节同余，具体可以看这篇或者猫(sunshine_cfbsl)在CSDN的博客；最后一部分个数显然小于p_i^{k_i}，直接暴力算就可以了。
需要注意的是由于我们算阶乘的每次递归都忽略了p_i，那么最后实际上要把每次的p_i次幂累乘起来，实现上可以在最后处理。

27.Fibonacci\ Sequence

斐波那契数列性质太多了，这里整理一些。
注意这里的斐波那契数列指的是f_1=a,f_2=b的任意数列。
矩阵

\begin{bmatrix}1&1&0\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}f_{i-1}\\f_{i-2}\\f_{i-3}\end{bmatrix}=\begin{bmatrix}f_{i}\\f_{i-1}\\f_{i-2}\end{bmatrix}

前缀和

\sum_{i=1}^nf_i=f_{n+2}-f_2 prove:f_i=f_{i-1}+f_{i-2} =f_{i-2}+f_{i-3}+f_{i-2} =f_{i-3}+f_{i-4}+f_{i-3}+f_{i-2} =\sum_{j=1}^{i-2}f_j+f_2 \therefore \sum_{i=1}^nf_i=f_{n+2}-f_2

性质
两个斐波那契数列加起来还是一个斐波那契数列。
(此条成立当且仅当f_1=1,f_2=1)f_n是偶数当且仅当3|n。

fib_{(a,b)}=(fib_a,fib_b)

28.Polynomial

多项式部分详见我的总结slide。

29.Lagrange\ Interpolation

拉格朗日插值法是个虽然很naive但我总是记不住的东西。现在终于可以写下来了。

1.暴力拉格朗日插值法

考虑知道一个k次多项式的k+1个点值，如何求这个多项式在某一点x的值呢？
实际上我们相当于求这个多项式的系数。
我们可以构造k+1个函数，对于每个函数f_i满足f_i(x_i)=y_i,f_i(x_j)=0。
尝试一下：

f_i(x)=\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}y_i

于是我们要求的多项式就可以线性结合了。

F=\sum_{i=0}^nf_i

用这种方式构造自然是O(k^2)的。

2.重心拉格朗日插值法

注意：在数学中这被成为重心拉格朗日插值公式第一型，也就是说，这并不是真正的重心拉格朗日插值公式。但在OI中，这个大概够用了。
有没有办法优化这个做法呢？
我们发现上面的式子有重复的部分，那么可以优化一下形式。

l=\prod_i(x-x_i),w_i=\frac{y_i}{\prod_{j\neq i}(x_i-x_j)} F=l\sum_{i=0}^n\frac{w_i}{x-x_i}

我们会发现这个式子还是\sout{O(n^2)}的。是有一些性质的：
对于动态加点的插值来说这是啥啊，我们只需要分别用O(1),O(n)的复杂度修改l,w，就可以在O(n)的时间内求出答案；
而对于横坐标连续（整数连续）的点值，我们可以进行一些优化，来达到整个式子O(k(\log k))的效果（O(\log k)是快速幂）：
简单来说，你可以发现w_i貌似是个阶乘的形式，是由一个负数阶乘和一个整数阶乘组合起来的。负数阶乘我们直接提出负号就可以了，只要事先O(k)预处理，就可以在O(k)的复杂度下求出这个多项式的系数。
自然数幂和是这个方法的一个经典应用。也就是求

\sum_{i=0}^ni^k,k\le O(k^2\ is\ banned\ and\ k\log k\ can\ pass)

我们设f_x=\sum_{i=0}^xi^k，那么x=n。
这其实是一个k+1次多项式，但我不会证。
然后直接插值就可以了？只要不想错式子就没有问题。

3.拉格朗日插值的性质

详细可以去看Angel\ Kitty的博客orz。
大概只需要记住这样的k次多项式是唯一的。

4.增加速度

其实是可以快速插值插出个多项式的。时间复杂度是O(n\log^2n)的。详见ymy博客。

5.如何实现

我后来发现我好像经常忘记如何实现插值，就稍微讲一下。
就是你直接把x=n,n就是你要求的f(n)。
然后就对着式子艹就可以了。

30.Li\ Chao's\ Segment\ Tree

李超线段树专门用来解决维护一些kx+b的直线或者线段之类的问题。
在一类dp方程是dp_x=b_ya_x+dp_y的时候，它也能以优秀的复杂度解决问题。(k=b_y,x=a_x,b=dp_y，所以这就是求x=a_x时的多条线段的最值，当然b_y,dp_y应该是可以调换的。)
李超线段树运用了标记永久化的思想来保证复杂度，插入线段的复杂度是O(\log^2)，插入直线及查询的复杂度是O(\log)。
具体的实现如下： 对于线段树上的每一个区间，我们维护这个区间在中点mid处最高的线段是的就是这么随意而不是网上许多人说的面积最大，这可以也只能保证它在这个区间内绝对有一块区域是不会被其他线段覆盖的。
我们先来考虑查询操作。同标记永久化的其它线段树一样，查询的区间要考虑到上面区间的影响。
但这里并不需要那么麻烦，在l==r时我们直接返回这条线段Adv[root]，其它情况下我们只要考虑这个区间[l,r]的Adv[root]和从子区间查询到的那条线段哪个更优就可以了，正确性应该是比较显然的——因为标记没有下放，有时候下面的线段不如上面这条优也是十分正常的。复杂度是很显然的O(\log)。
再来考虑如何插入一条线段。每次进入完全的子区间时，我们用一个cover函数来一次性解决这条线段所造成的影响。
首先我们先check一下哪条线段在目前这个区间比较优秀。如果是新的优秀，那我们先交换两条线段。
然后我们找一下两条线段的交点，如果在区间外，说明优势线段在整个区间都很优秀，直接return就可以了。
否则如果在区间左边，我们就往左递归，否则就往右递归。 于是插入的复杂度就是O(\log^2)了，因为每次cover会更新\log个区间。
这样我们就完成了维护。
注意交点这个东西可能精度有点问题，而且在mid处相交可能也有点细节。
因此我们换一种搞法：首先还是check，假设A线段是比较优秀的线段，B没那么优秀。
那么如果k_A<k_B，显然B线段的优秀在右边，我们就下方到右边；否则就去左边。当然如果相等就直接退出。
有一道板子题是[HEOI2013]Segment(P4097)。

``` 但是网上好多都像我这种 , 把线段基本上视作一条直线 , 从顶至底更新的时候 , 没有判断当前更新的线段 是否覆盖了x=k 这个范围 就导致答案失真... (ps : 这个一拍就错啦) 但是官方数据好像很神奇 竟然过啦 qwq ``` 我们考虑一下，其实是不会出现这种情况的。 因为当前的这个$Adv[root]$一定是完全覆盖了这条区间的某条线段，而且标记永久化是没有$pushup,pushdown$的，所以这种情况不会出现。~~Beng哥又双叒叕误人子弟了~~