算法备忘录

和信息竞赛有关的备忘录。

维护

维护说白了就是“保存信息”，是一种比较高端的说法。
信息问题一般都会用“询问-回答”的方式来出题。这类问题还可以细分为静态问题和动态问题，算法还有离线算法和在线算法之分。
对于每个询问，我们都会尝试去计算答案。有时候某些数值我们想直接调用，而不是重复计算。因此，我们会说去“维护”某个值，目的是快速得到答案。
举个例子，CQOI2018的交错序列。题目中对于一个(mathcal{1})字符不相邻的(mathcal{01})序列(lambda)，如果有(x)个(mathcal{0})，(y)个(mathcal{1})，求:

[ sumlimits_{|lambda|=n}x^ay^b pmod{m} ag{1-1} ]

题目不再赘述。我们要求的答案可以表示成:

[ sumlimits_{k=0}^a(dbinom{a}{k}n^a(-1)^{a-k}sumlimits_{|lambda|=n}y_{lambda}^{a+b-k}) ag{1-2} ]

由于(sumlimits_{|lambda|=n}y_{lambda}^{a+b-k})很不好计算，我们事先计算，对于不同的(k)把对应的值保存起来。

维护的方法有很多。一般主流的方法是使用数据结构。上面这道题使用的是动态规划。当然，这里到底能不能用“维护”一词还有待考证。

贡献

虽然信息学的数学计算基本都是和整数打交道，但整数还是有一定分类的。贡献一词一般是针对数值而言的。
a[i]=val;
来看这个最简单的代码块。这里的(i)是数组的下标，而(val)是数组元素对应的值。
有句俗话说得好，“不开(mathtt{long long})见祖宗”。为了防止整数“存不下”，我们会将大部分int变量换成long long。
但是，代码中的i是数组下标，不能用long long代替。这样的整数可以叫做“标号”，反之叫做“数值”。
一般的，对于两个变量(a_1,a_2)来说，由其中一个变量值推导出另外一个变量值，然后把这个值填进去，有点类似于“数值转移”。这种数值转移的多少我们就叫做这个变量的“贡献”。
比如说，(mathcal{01})序列(lambda)，要求计算其中(mathcal{0}) 的个数。我们说(mathcal{1})的贡献是0，因为它的存在不会使答案增加；而(mathcal{0})的贡献是1，因为多一个0，答案就增加1。

时间复杂度

我可能永远也学不会自己算这个东西。

假设一个算法的“计算次数”是(T(n))，(n)是数据的规模大小，如果存在两个正常数(c,n_0)使得(T(n_0) leq cf(n_0))，就称(T(n))在集合(O(f(n)))内，简记为(T(n)=O(f(n)))。其中(c)叫做这个算法的常数。所谓的卡常是一种算法优化策略，不会改变算法的时间复杂度，但可以降低算法的常数，提高速度。

时间复杂度可以帮助我们估计程序的运行时间。一般来说，我们会直接把(N)代入这个复杂度的表达式进行计算，并评估它的数量级。结果在(10^7)一下则说明这是一个很好的算法；结果在(10^8)以上则会越来越慢，往往在这种情况下，该算法只能称之为暴力算法，能得到部分分。

还有一些特殊的规定。我们常用(log n)代替(log_2n)。一些带有(log n)的时间复杂度的算法一般和“二分”“二叉树”有关。而(loglog n)则和一些更特殊的算法有关，比如埃氏筛。

但在大多数情况下，时间复杂度的表示会舍弃规范而表达出更多的信息。比如(O(2^3 log n))这个写法是不规范的，但它比(O(log n))的写法更加具有实际意义。这个时间复杂度表示的是斐波那契数列的矩阵快速幂优化，而(2^3)就是计算转移矩阵乘法的时间复杂度。

如果你想计算时间复杂度，可以借助下面的三个简单原理：

如果两个计算的过程有嵌套关系（比如说在每一次循环扫描的过程中还要排一次序），总时间复杂度是两者时间复杂度的乘积；
如果有多个计算过程按照顺序先后执行，那么取过程中“最大”的时间复杂度。（比如说先排序，再用单调队列，整个算法的时间复杂度就只能取(O(Nlog N))而不是(O(N))）
时间复杂度的优先级：(O(log N) < O(N) < O(N^p)(p>1) < O(a^N)(a >> 1))

教科书和有些题解往往会给出算法的时间复杂度。记住这个模型，下次就可以自己计算它们了。

一些展开

经常写一写这些有学术味的式子是一种很好的娱乐方式。

[ prod_{i=1}^n{(1+a_i)}=sum_{S subseteq {a_i}}prod_{k in S}k ag{2} ]

其中规定(S=varnothing)时，(prodlimits_{k in S}k=1)。

用这个可以结合容斥原理得出欧拉函数的表达式。

[ (sum_{i=1}^na_i)^2=sum_{i=1}^na_i^2+2sum_{1leq i < j leq n}a_ia_j ag{3} ]

[ (sum_{i=1}^na_i)^3=sum_{i=1}^na_i^3+sum_{1 leq i < j leq n}a_i^2a_j+sum_{1 leq i < j leq n}a_ia_j^2+sum_{1leq i <j < k leq n}a_ia_ja_k ]

[vdots ag{4} ]

事实上，这样的乘法有一个规律。如果乘积中含有(k)个项，即(k)个多项式，我们可以把每个项看成一个集合。每次从每个集合中选取(1)个单项，得到(k)个单项，我们就把这(k)个单项的乘积累加到答案中去。

不考虑合并同类项，我们展开可以得到(s_1s_2cdots s_k)个不同的求和项。其中(s_i)是原来每个项中单项的个数。这个定律叫做自由组合定律，事实上是一个遗传学定律。

首字母命名法

人名的一种简写读法。首先写出人名的拼音，然后将首字母直接拼接在一起。（如(zsj)就是一个首字母拼音法）首字母简写通常可以连接前缀(orz-)以表示对该人的膜拜，如(orzyyb)。

有一种特别的用法：作为模数。举个例子，如果我们答案要求对(10000007)取模，我们就可以令yyb=10000007；这样，在代码中我们就可以这样写：

sum = (sum + A[i]) % yyb

这个用法和(orzyyb)等效。这样做可以表示对学长的膜拜，并让代码显得颇有风趣。但是写题解或在学术场合不建议这样做，极大影响阅读体验。

一些植物衍生词

蒟蒻(jǔ ruò)，就是日常说的魔芋。像魔芋豆腐，蒟蒻果冻，都是非常好吃的食物。在这里表自谦。

蒯(kuǎi)，本指蒯草，多年生草本植物，叶子条形，花褐色。生长在水边或阴湿的地方。茎可用来编席，也可造纸。在这里表示“复制”的意思。多用于口语，其字较少见。

一些现代算法和数据结构。

如珂朵莉树，猫树。这些都是基于传统的数据结构和算法进行的升级。如珂朵莉树就是一种基于std::set的暴力数据结构，其实质是“动态分块”。这些数据结构都可以了解学习，有时在考场有一定几率赢得暴力分甚至全分。但就事论事，这些名字确实太蠢了。

和上面一样，这些数据结构最好不要出现在任何学术性质的文章中。如果可以的话，尽可能地对数据结构的优化进行说明。毕竟信息竞赛和信息学，计算科学还是有很大的差别的。

顺带一提，最近我正好做到了一道可以用珂朵莉树解决的问题。如果想了解更多，可以移步这里。