卡常数

程序被卡常数，一般指程序虽然渐进复杂度可以接受，但是由于实现/算法本身的时间常数因子较大，使得无法在OI/ICPC等算法竞赛规定的时限内运行结束。常数被称为计算机算法竞赛之中最神奇的一类数字，主要特点集中于令人捉摸不透，有时候会让水平很高的选手迷之超时或者超空间。普遍认为卡常数是埃及人Qa'a及后人发现的常数。也可认为是卡普雷卡尔(Kaprekar)常数的别称。主要用于求解括号序列问题。

名词解释

解决卡常数的方法比较多样化，主要为重复交题，拼人品让测评机快一点。很多信息学竞赛的专家也在研究如何解决这一问题，所以类似ZKW线段树   等可以有效减少常数的时间占用的方法也在不断被发现，今后还有很大的探索空间。

算法起源

据考证，卡（Qa'a）是古埃及第一王朝的最后一位法老。他发现并研究了一种常数，后世以他的名字叫做卡常数。卡特兰数的起源也是因为卡的后人与特兰克斯结婚，生下来的孩子就叫卡特兰，而他只是发表了祖传的家书而已。Sereja也是卡的后人，提出括号序列问题，也是从家书里得到的资料。然而Sereja为了不让这个秘密公开，于是隐瞒了这道题的真正做法。可是由于卡的后人不是各个都像卡特兰一样爱慕虚荣，这一算法也无法找到。“欲见贤人而不以其道，犹欲其入而闭之门也”。卡之常数的奥秘，需要以一颗诚心去追寻。

争议

有人怀疑其中的真实性，认为这一来源是用封建迷信来蛊惑人心。这对于理性的传播没有实在的帮助，但是在NOIP，各省OI中确实存在卡常数的应用。

另一方面的人认为著名数学家计算机科学家唐纳德·克努特写的一本史书《研究之美》，讲述的是一对情侣无意中得到了石器时代的智慧传承的故事。从书中可以看出石器时代的人有着非常先进的文明，然而正是因此，他们遭到了天谴，被落后的现代文明所取代，甚至连他们的宝贵文化也消失在了历史中。

也有考古资料显示，在我国华中地区出土了一系列关于卡氏家族的遗迹，可能和卡常数有关。不过更多的学者认为这只是一种称呼上的巧合；可以肯定的是，与卡常数有异曲同工之妙的卡巴斯基是卡氏家族的后代。

另一种说法

一些人认为“卡常”数在2009年由骆可强提出。

但更广为人知的是松松松最终将卡常数推广到了OI之中，其缓存优化载入埃及史册.

扩展卡常数

扩展卡常数（ExtendedKarp-de-ChantNumbers）

用于直接在线性时间内解决括号序列问题。

扩展卡常数实际上是卡常数的一个优化，主要实现如下：ai=1b−a∫abf2(t)dt∬B⃗ ⋅dS∏i=1ni;

这一算法由tarjan根据splay算法   的精髓在卡常数的基础上发展而来，可以解决涵盖数论、图论在内的多种经典难题，变形后还可用于高效求解网络流。扩展卡常数与另一种数据结构“球很好的很好的结合可以使得网络流在O(N+M+(N+M)sqrt(N+M))的时间复杂度内出解。

实验验证

可以参考《论程序底层优化的一些方法与技巧》。以及各种可以运用卡常数技巧的题目。经过多年的实验表明卡常数的威力无限，常常躲过了出题人的阴谋策略，成为蒟蒻到神犇的每一个级别的OIer/ICPCer不可多得的切题利器，将在未来的每一天，任何一台评测机上发挥其巨大的作用。看完本条目之后可以自己尝试写几个卡常数的代码！

适用范围

编程领域，当然对编程有兴趣的同学可以自己当一会编译器领会一下卡常数的好处！

发展简史

卡常数从无到有的伟大历史早在古埃及就已有发现，截止2018年被本页面的编辑者们发扬光大！

著名人物

卡 (Qa'a)

卡常数的创始人，为卡常数奠定了基础。

骆可强

将卡常数引入中国的第一人，是伟大的开创者。

zkw

中国民间卡常数代表，开创了田园派卡常数。

松松松

代表了卡常数的高峰，将卡常数深入系统底层，但后来转行电音。

经典例题

POJ 2228 Naptime

本题是一个显然的动态规划题目。设计状态时，用f[i,j,1]表示第i段时间为止，已睡去j个时间段，且第i段时间睡觉获得的最大效用。反之，f[i,j,0]表示上述状态下[i]第i段时间不睡觉能获得的最大效用值。

状态转移方程如下：

f[i,j,0] = Max{f[i-1,j,0]，f[i-1,j,1]}

f[i,j,1] = Max{f[i-1,j-1,0],f[i-1,j-1,1]+u[i]}

具体就不用多解释了，这题的关键不在方程上，而在于的是环形Dp的处理。

上述方程从i=1开始顺推，推出的只能是第一段时间开始睡或者第一段时间没有睡的最大效用值，换句话说，就是无论如何没有把u[1]加入这个最大值中，但是题目要求有可能让我们把u[1]加入进去，所以只需考虑一下u[i]必被加入的情况。处理的方法就是，之前的初态为f[1,1,1]:=0;和f[1,0,0]:=0;其余f值均为-maxlongint(即将第一秒睡不睡的值都记为0)，那么，我们只需把初态记为f[1,1,1]:=0;其余值均记为-maxlongint，然后再将f[n,b,1]+u[1]与原来更新出来的的ans值作比较即可。

注意：本题如果按照上述方程进行会占用较大内存，造成空间浪费，所以需要滚动数组优化。

有部分人采用卡常数的策略无优化过此题。

BZOJ3815

在某个诡异的地方，有一座智慧之城，那里的人民平均智商为 192，智商低于 150 的人都被称为弱智。智慧之城的市长名叫卡常（Karp-de-Chant），他 12 岁时在智慧之城中心大学 Cross Institute 获得博士学位，两年后发明了一种数列 —— 卡常数（Karp-de-Chant Number），该数列可用来解决或优化数论、图论等领域的多种经典难题。后来，卡常数被 Trajan（智慧之城的副市长）用 spaly 树进行扩展后，威力大大增加，可以在线性时间内解决各种网络流问题和其它一些难题。卡常和 Trajan 因此分别被选为正、副市长，他们和智慧之城内的另一些智者一起，领导人民共同建设人类智慧，发挥创造和改进的能力。

然而某一天，智慧之城突然受到了反人类智慧者的袭击，反人类智慧者在城内设置了 N 个摄像头（由于他们的智商很低，只会用摄像头这种垃圾玩意），企图监视城内的人们。卡常、Trajan 决定找到这些摄像头并摧毁它们。

智慧之城里有一个用扩展卡常数原理设计的发射器，将其放在合适位置并设置半径以后，所有位于球心为这个发射器的位置、半径为指定值的球面上的目标都能被发现。在卡常、Trajan 的带领下，智慧之城的人们用这个发射器进行了若干次实验，并发现了一些摄像头的位置。比较囧的是，每次发射都能且仅能发现一个摄像头，但是，反馈回来的结果貌似有些不对劲……

后来人们终于找到了这 N 个摄像头的位置，并发他们用发射器进行实验的过程中，某些摄像头被移位——这就是导致反馈结果不对劲的原因。但是，在对实验结果进行分析的时候，人们却肿么也回忆不起每次实验发现的摄像头是哪个了（可能是遭遇了灵异事件导致脑抽），只知道每次实验时发射器的位置和半径。你的任务就是，根据实验数据（为了防止被反人类智慧者窃取，已经进行了加密）找出每次实验时被发射器找到的摄像头的编号。

一道kdtree.

1.强制在线不能用牛顿迭代解方程精度不够；

2.信息维护可能会退化

3.需要卡常数

BZOJ3583

这道题首先可以设表示走了j步以后在第i座城市的方案数

然后可以想到一个朴素的DP算法。

题目中的K是干什么用的？

若我们直接把in和out合并成一个W矩阵使得代表一步从i走到j的方案数不是更方便吗？

然后我们可以愉悦地发现，正好就是表示的是从用T步从i走到j的方案数。

那么我们只要再加一个计数器然后搞一搞矩乘就可以得到题目中要求的答案了。

但这样的复杂度是的，只能拿60分。

嗯我在考场上面就这样写的但是出题人丧心病狂地卡了常数所以只有30

卡常数策略

经实际检测

这样的语句比下面的语句快了一倍左右

那么怎么过掉这道题呢。

可以发现，若我们把in矩阵旋转一下变成in'矩阵，那么，所以。

于是就可以在要求时间内过掉所有数据