名詞解釋
解決卡常數的方法比較多樣化，主要為重複交題，拼人品讓測評機快一點。很多信息學競賽的專家也在研究如何解決這一問題，所以類似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'矩陣，那么，所以。
於是就可以在要求時間內過掉所有數據
