玄学算法/精彩DS总结 Vaiz
teafrogsf
2018-08-06 17:26:05
## $21.Bit\ DP$
（摘自zjBrave_shadow博客）
套路：
我们常常是要求$\le$n的有多少个满足要求的数。
这个限制有些恶心，我们需要多一位来看是否被限制。
我们一般按位考虑，令$dp[i][0/1]$为到从高到低考虑到第$i$位，当前有/没被$n$限制。
我们考虑把$n$按位拆下来，变成一个数组$lim[i]$，然后取出$n$的位数$Bit$。
每次考虑后一位放什么数字就行了。具体实现如下（用刷表法方便转移）：
```cpp
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];//这里是<的原因是，
```
然后最后的答案就是
```cpp
ans = dp[Bit][0] + dp[Bit][1];
```
不难发现这样写，每个位数的数都会被考虑到。因为我们枚举的时候允许了前缀$0$
的存在。
并且如果存在前缀$0$那么后面的所有数都不会存在限制了，可以随便填。
但是注意这样的话，全部为$0$的也会考虑进去，我们平常要考虑是否$-1$就行了。
## $22.Convex\ Optimization$
凸优化是$APIO2018$的讲课内容，预计将来的一段时间内会成为~~神仙难度的~~热点。详情可以见我的slide。
## $23.Constant\ Optimization$
1.在开O2的时候，循环语句在只有一句话的时候非常快，我们可以将原本的多个语句通过预处理等形式让语句只有一句，可以大大提高循环效率。
2.你可以通过计算
```cpp
unsigned long long
```
爆了多少次，再在最后减回来。
3.(与4一起摘自__debug博客)
```cpp
std::string procStatus()
{
std::ifstream t("/proc/self/status");
return std::string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
```
```cpp
//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}$的部分乘积，以这个部分的个数为循环节同余，具体可以看[这篇](https://blog.csdn.net/clove_unique/article/details/54571216)或者猫(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](https://www.cnblogs.com/ECJTUACM-873284962/p/6833391.html)。
大概只需要记住这样的$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)$。
$P.S.\ Faker\_Beng$的博客提到了一个问题：
```
但是网上好多都像我这种 , 把线段基本上视作一条直线 ,
从顶至底更新的时候 , 没有判断当前更新的线段 是否覆盖了x=k
这个范围 就导致答案失真... (ps : 这个一拍就错啦)
但是官方数据好像很神奇 竟然过啦 qwq
```
我们考虑一下，其实是不会出现这种情况的。
因为当前的这个$Adv[root]$一定是完全覆盖了这条区间的某条线段，而且标记永久化是没有$pushup,pushdown$的，所以这种情况不会出现。~~Beng哥又双叒叕误人子弟了~~