有用和没有用的常数优化技巧
JohnVictor
·
·
个人记录
0、写在前面
这里写的是不对代码本质进行改变的常数优化。比如线段树转树状数组就是改变了本质。（当然避免递归对常数的优化是很大的）
1、取模常数优化
这个主要有两个地方：（1）取模次数优化；（2）取模常数优化。
（1）取模次数优化：
很多时候模数都是 10^9 级别的，但是 unsigned long long 能开到 1.8 \times 10^{19}。这就表明，如果一个数（需要取模）是形如 \sum a_ib_i 的形式的话，完全可以减少取模次数。一个简单的运用是矩阵，例子如下：
struct jj
{
ll a[105][105];char vis[105][105];
}a;
ll n;
jj mul(jj x,jj y)
{
jj res;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
res.a[i][j]=res.vis[i][j]=0;
for(int k=1;k<=n;k++)
{
res.a[i][j]+=x.a[i][k]*y.a[k][j];
++res.vis[i][j];
if(res.vis[i][j]>=18)res.a[i][j]%=p,res.vis[i][j]=0;
}
res.a[i][j]%=p;
}
}
return res;
}
这里的 vis 数组表示被加的次数，由于这里能开到 ull 的级别，所以加 18 次去一次膜。亲测快 2 倍左右（因为这样并没有减少乘法的常数）。
当然如果题目中能直接优化是最好的。比如出题人让你取模，其实答案完全能用 long long 装下。这种情况下不取模通常是会飞快的。
**注意，如果模数给定，最快的方法就是加上 `const` 关键字。**
然而经常有出题人为了防止你分块打表，所以模数不给定。这时候取模就有优化的空间了。
原理大概是：取模的本质是一次除法，一次乘法，和一次减法（忽略不计）。那么如果把除法转换成乘法，那么就会变快，这也是编译器对于给定模数的优化原理。
这同时也代表了，如果你平常用的 `%4` 写成 `&3` 是几乎没有任何优化作用的，因为编译器帮你优化好了。
对于不定的模数，有 [berrett模乘](https://www.luogu.com.cn/problem/P6276) 和 [exactdiv](https://min-25.hatenablog.com/entry/2017/08/20/171214)。（sto Min_25 Orz）
感性理解一下原理：如果我要计算 $a/b$（其中 $b$ 给定），这很慢；如果我证明了他就是 $ac/d$（其中 $c,d$ 是常数），那么在 $d$ 是 $2$ 的次幂时除法运算变为了位运算，实现了加速。
这里给出模板代码（这个能在前面的链接中找到，但是为了避免~~像我这样的人~~链接打不开放出来）
berrett 模乘（by KACTL）：
```cpp
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
```
其中 `reduce` 能把一个大数取模，这里的大数不大于模数的平方。`Fastmod(x)` 是设定模数为 $x$。
exactdiv（by Min_25）：
```cpp
template <typename T>
struct ExactDiv {
ExactDiv() {}
ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) {}
T mul_inv(T n) {
T x = n;
for (int i = 0; i < 5; ++i) x *= 2 - n * x;
return x;
}
friend T operator / (T n, ExactDiv d) { return n * d.i; };
bool divide(T n) { return n * this->i <= this->t; }
T t, i;
};
```
用法和上面类似，调用 `divide` 可以获取是否整除。
上面两种方法的效果上，前一种会快 $3$ 倍，后一种快 $9$ 倍。
**再次声明，`const` 做的事情和这个类似，但是他会把预处理出的数也设置为常数，所以会更快。**
与这个类似的，用加法次数换乘法次数也能一定程度上优化常数。
### $2$、使用条件恒等式进行优化。
这个标题是不是有点 深奥？其实很基本的啦。
意思就是一个不是所有时候都成立的等式。
比如 $(a+b)\ mod \ p=a+b\geq p?a+b-p:a+b$。这个只有在 $a,b \le p$ 的时候才成立，所以编译器并不会帮你优化。
反之，拿线段树中大家喜欢用的 `x<<1|1` 举例，理论上 `<<1` 并不比 `*2` 快，因为恒成立；比较厉害的编译器可能能帮你把 `x*2+1` 直接优化成 `x<<1|1`，这个我不清楚。
顺便说一句，上面那个东西包装成函数会比较慢，建议 `define` 掉。
然而 `define` 容易挂，一种比较好的方式使包装成一个 `struct Int` 表示 $mod \ p$ 意义下的整数。
大概就是这样：
```cpp
struct Int{
int a;}
```
然后封装的 `+,-` 号中是带有优化的取模。
在 $x,y$ 都是 `int` 类型且非负时，可以用 `x-y>>31` 代替 `<`，能快 $3-5$ 倍。
### $3$、优化内存访问常数
理论上，下面两段代码速度差距很大：
```cpp
//1
for(int i=1;i<=1e6;i++)++a[i];
//2
for(int i=1;i<=1e6;i++)++a[i*i%1000000];
```
理论上都进行了 $10^6$ 次运算，但是有差距，这个差距就是内存访问的时间差距。
所以在你复杂度是正确但是一直过不了题的时候，尤其是这题是 `dp` 题的时候，可以考虑下列两种方法：
（1）换用刷表法/填表法。
（2）交换数组各维的意义。比如 `dp[l][r]` 改写成 `dp[r][l]` 在某些题目中有奇效，不要脸宣传 [屑题](https://www.luogu.com.cn/problem/P6563)。
这个原理就是改变了内存访问顺序使得访问更连续，高斯消元的优化也是一样的。
### $4$、循环展开
好了轻工业到此结束，我们开始重工业。
前面的取模优化中的取模还是不够快，其实已经不是慢在取模上了，取模次数大幅度减少，但是在计算卷积的时候没有并行计算。所以这里可以循环展开优化常数/shake。（然而太不实用了）
注意展开的东西必须是简单的。如果你同时运行 $4$ 个 `exactdiv` 会造成负优化的，但是同时计算四个乘法会快 $4$ 倍。
要讲的东西不多，例题： [多项式多点求值](https://www.luogu.com.cn/problem/P5050)。请用秦九韶算法 `AC` 本题。
当然这已经 $SPFA$ 了，~~为啥不指令集让他 $NOIP$ 呢？~~
### $114514$、玄学常数优化
众所周知，卡不过的时候可以干这么几件事情：
（1）女装；（1）深夜提交；（4）膜拜大佬；（5）加各种 `inline`，`register`；（1）`srand (1******7)`；（4）代码中加上 `return 1*******7`。