卡常！

listgv · 2025-10-20 21:02:45 · 休闲·娱乐

众所周知，作为一名OIer，我们常常遇到需要卡常的情况，比如：

打非多项式复杂度算法时
编写名竞测号器时
~~不想写分治FFT时~~

好吧，在平时做题的时候还是尽量不要写暴力卡常的。在考试时候如果正解写不出来还是可以考虑这个的。

内容仅供参考，都是用我手上的这台破机子跑出来的。

理论层

循环展开

循环展开是一个非常好写而且增益极大的卡常方法，适用于大部分情况。

什么，你问bitset在哪，那玩意不仅常数小还稳定还好写已经升华为正解之流了。

循环展开是这个样子的：

比如你原来代码长这样

int ans=0;
for(int i=1;i<=n;++i){
    ans+=i;
}

循环展开一下就可以得到这个

int ans0=0,ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0,ans7=0;
for(int i=8;i<=n;i+=8){
    ans0+=i;
    ans1+=i-1;
    ans2+=i-2;
    ans3+=i-3;
    ans4+=i-4;
    ans5+=i-5;
    ans6+=i-6;
    ans7+=i-7;
}
switch(n&7){
    case 7:ans6+=n-6;
    case 6:ans5+=n-5;
    case 5:ans4+=n-4;
    case 4:ans3+=n-3;
    case 3:ans2+=n-2;
    case 2:ans1+=n-1;
    case 1:ans0+=n;
}

n=1e9(开O2)时，前一段代码需要680\~920ms，后一段代码需要330\~430ms，可以看出加成非常大。

前面的for把循环一拆八，促进指令级并发，从而提升效率

最后那个switch把一些漏掉的值补上，也可以换if等。这个东西不怎么需要卡常，因为一般运行次数不多。

指令级并发是指通过通过流⽔线等技术实现多条指令同时并⾏执⾏的并⾏技术，具体什么原理比较复杂，你只需要知道数据的相关性会影响指令级并发就可以了。

数据的相关性有很多种，你只要知道这几个会增加相关性就行了：

使用相同变量
前面语句的结果被后面用到

比如，你这么写循环展开：

int ans0=0,ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0,ans7=0;
for(int i=8;i<=n;i+=8){
    ans0+=i;
    ans0+=i-1;
    ans0+=i-2;
    ans0+=i-3;
    ans0+=i-4;
    ans0+=i-5;
    ans0+=i-6;
    ans0+=i-7;
}
switch(n&7){
    case 7:ans0+=n-6;
    case 6:ans0+=n-5;
    case 5:ans0+=n-4;
    case 4:ans0+=n-3;
    case 3:ans0+=n-2;
    case 2:ans0+=n-1;
    case 1:ans0+=n;
}

不开O2会慢，但O2会把for里一坨优化成ans0+=i+i-1+i-2+i-3+i-4+i-5+i-6+i-7;之类的，加上我的机子比较奇怪，跑的更快。

能合并还是要合并的，毕竟+=次数多了也影响常数。

卡常！

理论层

循环展开

缓存