目录

  1. 引言
    1. 数学
      1. 数论
        1. 质因数分解法
          1. Pollard-Rho 因数分解法
          2. 线性筛质因数分解法
          3. 变上界质因数分解法
        2. 素数判定法
          1. Miller-Robin判素法
      2. 黑科技公式
        1. 下取整累积公式
        2. 取模公式
        3. 调和级数定理
        4. 异或不等式
        5. 分块公式
        6. 上/下取整不等式
    2. 数据结构
      1. ST表
        1. 计算极值覆盖区
      2. 单调栈
        1. 计算极值覆盖区
    3. 枚举
      1. 枚举子集
    4. 编程相关
      1. 常数优化
        1. 适当运用register关键字
      2. 内存优化
        1. 减少额外占用

引言

在这神秘的光芒背后,有着怎样的奥秘?(纯胡扯

黑科技大概指的就是我们编程中的一些技巧,无法单独开一篇文章进行记录,于是汇总到这里

这篇文章很早以前就开了,只是一直没有内容,下面我就来填充一下

数学

数论

下面的黑科技先只写描述,代码留坑待补

质因数分解法

Pollard-Rho 因数分解法

我们使用一个随机函数$F(x)$生成随机数列$a_1, a_2, \cdots, a_n$,其中,$F(x) = (ax^2 + c) \bmod n$

然后,我们使用两个对于这个数列而言的指针(由于数列项的数量过大无法保存),其中一个的迭代速度是另一个的二倍,即$a = F(a), b = F(F(b))$

然后,我们求出$d = gcd(\mid a - b \mid, n)$,如果$d > 1$,那么我们就找到了一个$n$的因子$d$

如果发现$b == a$,这说明数列出现循环,而我们此时发现了这一点,我们重新随机随机函数的那两个系数,然后重新随机进行分解

这样,我们可以在$O(n^{\frac{1}{4}})$实现对大数的质因数分解

线性筛质因数分解法

首先我们先跑一遍线性筛,以$son[i]$记录把$i$筛掉的最小的质数

分解质因数的时候,不停地$n=n/son[n]$来分解

可以证明复杂度是单次$O(logn)$:每迭代一次,$n$被除以$son[n]$,而$son[n]$最小为$2$,故时间复杂度不超过$O(logn)$

变上界质因数分解法

众所周知,我们正常人在因数分解的时候,我们都是采用$O(\sqrt{n})$的算法进行暴力分解的,我们从小到大枚举质因数,判断能否整除$n$,然后再进行相应分解即可,直到枚举的质因数大于了$\sqrt{n}$,就停止,如果此时$n$不为$1$,那么它一定是一个质数(这应该很显然)

但是,我们发现,随着分解的进行,$n$在不断地减小,这就是说,$\sqrt{n}$这个上界也是不断地减小的,我们每次做完一个质因数的分解,直接更新上界,用当前的$\sqrt{n}$作为上界,然后继续上面的操作即可

经实测这个方法优化的效果十分明显,具体证明则是玄学

素数判定法

Miller-Robin判素法

具体操作方法的讲解网上应该已经很多了,本处暂略,时间复杂度:$O( \log n)$,适合大数判素或多组询问

黑科技公式

下取整累积公式

可以用下文的下取整不等式证明

取模公式

这个公式很重要,在许多只有取模存在的式子中,这个公式往往是解题的关键

调和级数定理

可以用微积分证明

异或不等式

把异或运算转化为代数表达

分块公式

我们现在已知$x$和$n$,要求最大的$y$满足

那么

上/下取整不等式

还有什么呢?到时候再说吧。。。

数据结构

ST表

计算极值覆盖区

极值覆盖区,就是一个元素作为一个区间里的极值时,这个满足条件的区间的范围,或者是对于一个元素来说,如果它是作为最大值出现的,那么我们需要找到它左端第一个大于它的元素的位置以及右端第一个大于它的元素的位置

我们可以这样表示这个范围,对于第$i$个元素,我们用$l[i]$表示$i$能覆盖的最左端,$r[i]$表示$i$能覆盖的最右端

那么,对于所有满足$l[i] \leq l \leq i$并且$i \leq r \leq r[i]$的区间$[l, r]$来说,第$i$个元素的值都是这个区间里的极值

我们对于这个问题,可以使用二分+线段树在$O(log^2n)$的时间内处理每一个元素的覆盖区间,但是这显然太弱了是不是?

我们可以考虑使用ST表来优化这个问题的复杂度,我们可以用$O(n \log n)$的复杂度预处理ST表,然后对于每个元素使用$O(\log n)$的复杂度求出边界,这样总共的复杂度就是$O(n \log n)$的,编程复杂度远低于上面的那个方法

其实这个问题还有一个$O(n)$的方法,然而我刚想到。。。所以就在下面说吧

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int le[maxn][bit];
int ri[maxn][bit];
int line[maxn];
int n;
int main(){
rep(i, 1, n) le[i][0] = line[i], ri[i][0] = line[i];
rep(i, 1, n) rep(j, 1, bit - 1) {
if (i - two[j - 1] >= 1) le[i][j] = min(le[i - two[j - 1]][j - 1], le[i][j - 1]);
else le[i][j] = -INF;
if (i + two[j - 1] <= n) ri[i][j] = min(ri[i + two[j - 1]][j - 1], ri[i][j - 1]);
else ri[i][j] = -INF;
}//初始化ST表
rep(i, 1, n){
int x = i;
int y = i;
int op = line[i];
per(j, bit - 1, 0){
if (le[x][j] >= op) x -= two[j];
if (ri[y][j] >= op) y += two[j];
}
l[i] = x + 1, r[i] = y - 1;
}//通过ST表不断跳跃寻找边界
return 0;
}

代码还是十分简单的

单调栈

计算极值覆盖区

接着ST表那里的讲解,这里有一个利用单调栈进行$O(n)$处理的玩法

假设每个元素是作为最大值出现的,我们先考虑求出每个位置的$i$的$r[i]$,我们维护一个单调递减的单调栈,从左扫到右,每次扫到一个元素,把所有小于这个元素的元素弹出,并把它们的$r[i]$记录为当前扫到的位置减一,然后我们把扫到的这个元素加入栈中,继续上述扫描,然后就可以求出所有的$r[i]$啦

关于正确性的证明,显然是对的啊。。。于是复杂度就都是$O(n)$了,又明显优于ST表的做法,而且达到了理论下界

不要和我说可以用一些已经推出的元素推导未知的来达到更优的复杂度,那样没什么意义。。。至少对于这个问题来说是这样,因为这个问题本身往往只是一个子问题,不值得使用过于复杂的处理

果然还是这样探究问题的未知的更优答案,能使人有更大的成就感啊

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
stack<int> s;
int line[maxn];
int n;
int main(){
rep(i, 1, n){
int op = line[i];
while (!s.empty() && line[s.top()] > op) r[s.top()] = i - 1, s.pop();
s.push(i);
}
while (!s.empty()) r[s.top()] = n, s.pop();
per(i, n, 1){
int op = line[i];
while (!s.empty() && line[s.top()] > op) l[s.top()] = i + 1, s.pop();
s.push(i);
}
while (!s.empty()) l[s.top()] = 1, s.pop();
return 0;
}

代码又简单了一些。。。

枚举

枚举子集

这里有一个十分简洁高上的写法:

1
2
3
for (int x = S; x; x = (x - 1) & S){
//do something...
}

感觉证明非常简单,首先,我们可以考虑$S$的二进制没有零的特殊情况,这样我们就相当于从$S$不断地减一,一直减到零,那么中间经过的这些数值很显然肯定是$S$的子集,如果$S$的二进制表示中有零存在,那么我们每次进行一个与操作,相当于是直接跳过了$S$的某一位为零,而$x$的那一位却为$1$的不合法情况,由于跳过的这些情况都是比剩下的所有合法情况数值要大的(看成十进制的数值),所以我们不会跳过合法情况

这样,就相当于我们的$x$经过且仅经过了所有合法的情况,这样就是对$S$的子集枚举啦

编程相关

常数优化

适当运用register关键字

register关键字的作用是将后面声明的变量放入系统CPU的寄存器中,使得变量的操作速度快得飞起,但是我们只能将int类型的单个变量用这种方法声明,由于系统寄存器很小,所以建议不要同时对超过三个int变量进行register声明,否则反而会降低运行速度

所以,我们采取用完回收的原则,可以宏定义一种优化的for循环语句:

1
#define rep(i, l, r) for (register int i = l; i <= r; i++)

然后以后用rep(i, l, r)代替for循环就行了,实测可以大幅提高程序运行速度

内存优化

减少额外占用

实测发现,在使用较多的#include语句以及使用这个语句using namespace std;时,我们的程序会产生许多的额外内存开销,这对于卡内存的题目而言是非常不利的