卡常數

程式被卡常數，一般指程式雖然漸進複雜度可以接受，但是由於實現/算法本身的時間常數因子較大，使得無法在OI/ICPC等算法競賽規定的時限內運行結束。

常數被稱為計算機算法競賽之中最神奇的一類數字，主要特點集中於令人捉摸不透，有時候會讓水平很高的選手迷之逾時或者超空間。

基本介紹

• 中文名：卡常數
• 外文名：Karp-de-Chant Number
• 別稱：卡場數、卡殼(qiào)數、卡式家族數、底層最佳化
• 表達式：ai=1b−a∫abf2(t)dt∬B⃗ ⋅dS∏i=1ni
• 提出者：卡常
• 提出時間：古埃及
• 套用學科：計算機
• 適用領域範圍：信息學競賽(OI，ICPC)，程式設計套用
• 特殊功能：解決一切常數問題
• 使用前置技能：一定的代碼水平
• 拼    音：qiǎ cháng shù

名詞解釋

解決卡常數的方法比較多樣化，主要為重複交題，拼人品讓測評機快一點。很多信息學競賽的專家也在研究如何解決這一問題，所以類似ZKW線段樹等可以有效減少常數的時間占用的方法也在不斷被創造，今後還有很大的探索空間。

算法起源

據考證，卡（Qa'a）是古埃及第一王朝的最後一位法老。他發現並研究了一種常數，後世以他的名字叫做卡常數。卡特蘭數的起源也是因為卡的後人與特蘭克斯結婚，生下來的孩子就叫卡特蘭，而他只是發表了祖傳的家書而已。Sereja也是卡的後人，提出括弧序列問題，也是從家書里得到的資料。然而Sereja為了不讓這個秘密公開，於是隱瞞了這道題的真正做法。可是由於卡的後人不是各個都像卡特蘭一樣愛慕虛榮，這一算法也無法找到。“欲見賢人而不以其道，猶欲其入而閉之門也”。卡之常數的奧秘，需要以一顆誠心去追尋。

有人懷疑其中的真實性，認為這一來源是用封建迷信來蠱惑人心。這對於理性的傳播沒有實在的幫助，但是在NOIP，各省OI中確實存在卡常數的套用。

另一方面的人認為著名數學家計算機科學家唐納德·克努特寫的一本史書《研究之美》，講述的是一對情侶無意中得到了石器時代的智慧傳承的故事。從書中可以看出石器時代的人有著非常先進的文明，然而正是因此，他們遭到了天譴，被落後的現代文明所取代，甚至連他們的寶貴文化也消失在了歷史中。

也有考古資料顯示，在我國華中地區出土了一系列關於卡氏家族的遺蹟，可能和卡常數有關。不過更多的學者認為這只是一種稱呼上的巧合；可以肯定的是，與卡常數有異曲同工之妙的卡巴斯基是卡氏家族的後代。

擴展卡常數

擴展卡常數（ExtendedKarp-de-ChantNumbers）用於直接在線性時間內解決括弧序列問題。

擴展卡常數實際上是卡常數的一個最佳化，主要實現如下：ai=1b−a∫abf2(t)dt∬B⃗ ⋅dS∏i=1ni;這一算法由tarjan根據splay算法的精髓在卡常數的基礎上發展而來，可以解決涵蓋數論、圖論在內的多種經典難題，變形後還可用於高效求解網路流。擴展卡常數與另一種數據結構“球很好的很好的結合可以使得網路流在O(N+M+(N+M)sqrt(N+M))的時間複雜度內出解。

經典例題

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

卡常數策略

經實際檢測

for (int i = 0; i <= K; i++)  for (int j = 0; j <= K; j++)    for (int k = 0; k <= K; k++)    {      r.a[i][j] += a[i][k] * x.a[k][j];      if (r.a[i][j] >= 1ll << 62 || k == K) r.a[i][j] %= mod;    }

這樣的語句比下面的語句快了一倍左右

for (int i = 0; i <= K; i++)  for (int j = 0; j <= K; j++)    for (int k = 0; k <= K; k++)      r.a[i][j] = (r.a[i][j] + a[i][k] * x.a[k][j] % mod) % mod;

那么怎么過掉這道題呢。
可以發現，若我們把in矩陣旋轉一下變成in'矩陣，那么，所以。
於是就可以在要求時間內過掉所有數據