最近帶學生刷《信息學奧賽一本通》的時候1313這道“位數問題”幾乎隔一陣子就有人卡住。題面很短在所有的N位數中有多少個數中含有偶數個數字3答案對12345取模N給到1000。第一眼看過去像小學奧數腦筋急轉彎但放到“遞推算法”這個章節(jié)里它其實是一道非常典型的狀態(tài)設計題核心考兩個點遞推狀態(tài)怎么定義以及前導零怎么處理。對準備CSP-J/S、或者剛學完遞推想刷題鞏固的選手來說這一題值得徹底吃透。這篇我就用最容易理解的方式把從題意拆解到AC代碼再到延伸擴展的完整過程講清楚。1. 題目到底在問什么別被“位數”兩個字帶偏1.1 題面還原與三個容易漏掉的細節(jié)標準題面是這樣的在所有的N位數中有多少個數中有偶數個數字3由于結果可能很大你只需要輸出這個答案對12345取余數的值。輸入一個整數N輸出一個整數答案。這句話里藏著三個細節(jié)初次做的人很容易忽略第一“N位數”嚴格來說就是N位的正整數最高位不能是0。三位數指的是100到999而不是000到999。這一點直接關系到最后的答案也是網上很多題解吵來吵去的地方。第二“含有偶數個數字3”里的偶數包括0。也就是說一個數里一個3都沒有也算“偶數個3”。這個細節(jié)不理解的話n1的答案你就沒法算對。第三為什么要對12345取模因為這題的答案會非常大。N1000的時候真值是一個幾千位的天文數字不取模連long long都裝不下。取模既是題目約束也是在暗示你N很大別想暴力。1.2 先手推兩個小數據做題之前先手動算兩個小規(guī)模的情況能幫你驗證后面所有推導。N1時一位正整數是1到9。這9個數里只有數字3含有一個3是奇數個其余8個數1、2、4、5、6、7、8、9都不含30個3算偶數個。所以答案是8。N2時兩位數從10到99。先看完全不含3的數十位可以是1、2、4、5、6、7、8、9共8種個位可以是0、1、2、4、5、6、7、8、9共9種。兩者相乘得到72個。再看含有偶數個3且不是0個的這里只能是“含有兩個3”的情況也就是一個數是33只有1個。所以答案等于72加1是73。這兩個結果記下來后面代碼跑出來的答案必須和它們一致。1.3 為什么暴力枚舉必掛有些新手看到這題的第一反應是寫個循環(huán)從10^(N-1)枚舉到10^N-1數一下含3個數然后統計。這個思路在小數據下完全正確但N1000時你要訪問10的999次方量級的數這個規(guī)模比宇宙中的粒子數還多好幾個數量級程序跑完地球毀滅都不可能出結果。所以題目放在“遞推算法”這一章就是在告訴你別枚舉去找規(guī)律讓第i步的結果能從第i-1步的結果直接推出來。計數類問題一旦規(guī)模變大第一反應永遠是“能不能遞推”而不是“能不能枚舉”。2. 核心思路用“允許前導零的字符串”做遞推2.1 狀態(tài)設計dp[i][0]和dp[i][1]真正動手遞推之前先做一個看起來很“繞”的變換暫時把“N位數”放寬成“長度為i的十進制數字串允許第一位是0”。定義兩個狀態(tài)dp[i][0]長度為i的串中數字3出現偶數次的串的數量dp[i][1]長度為i的串中數字3出現奇數次的串的數量。這里的“串”是允許前導零的。比如i2時“03”和“33”都算長度為2的串。為什么要這樣放寬這是我個人認為這道題最值得學的地方。你想啊如果嚴格按“首位不能為0”來遞推每次往最高位放數字的時候都要額外判斷“當前是不是第一位”。這一判斷不僅寫起來麻煩還容易漏。而如果先假設每一位都能放0到9任意一個數字整個遞推過程就非常干凈因為每一位的可選數字數都一樣。算完之后我們只需要把所有“最高位是0”的串統一減掉就行。這個“先算全集再扣掉不合法的子集”的思路在計數題里非常通用。2.2 遞推式的完整推導現在考慮從長度為i-1的串擴展成長為i的串。所謂擴展就是在原串末尾追加一位數字。檢查一下追加什么數字會影響偶奇性。如果追加的數字是3只有1種放法。原來偶數個3的串追加后變成奇數個3原來奇數個3的串追加后變成偶數個3。用式子表達就是從dp[i-1][1]轉移到dp[i][0]從dp[i-1][0]轉移到dp[i][1]。如果追加的是0、1、2、4、5、6、7、8、9一共9種放法。這些數字不會改變3的個數。所以dp[i][0]需要加上dp[i-1][0]乘以9dp[i][1]需要加上dp[i-1][1]乘以9。把兩種情況合并就得到核心遞推式dp[i][0] dp[i-1][1] dp[i-1][0] * 9 dp[i][1] dp[i-1][0] dp[i-1][1] * 9所有中間結果對12345取模。我給初學者講這個式子的時候喜歡把它比喻成開關問題數字3就是墻上的一個開關遇到一次3就按一下奇偶性翻轉遇到其他數字等于什么都沒發(fā)生。你只關心最后燈是開還是關不關心之前按了多少次。這就是為什么狀態(tài)只有0和1兩維而不是記錄“具體出現了幾個3”——具體數字對答案沒影響奇偶性就足夠。2.3 邊界為什么要從空串開始邊界條件我喜歡寫成dp[0][0] 1dp[0][1] 0。含義是長度為0的串只有空串一種里面0個3而0是偶數所以它屬于“偶數個3”這一類。這個邊界看起來抽象但非常優(yōu)雅。它讓循環(huán)可以從i1直接跑到iN不需要對N1做特殊判斷。有些資料把邊界寫成dp[1][0]9、dp[1][1]1那樣循環(huán)要從i2開始并且算N1時要單開邏輯。這兩種寫法在絕大多數數據下結果一樣但“空串起步”在邏輯上最完整后面講答案計算時你會看到它的好處。3. 從“所有串”到“真N位數”減去首位為0的計數3.1 答案為什么是dp[n][0]減dp[n-1][0]dp[n][0]統計的是所有長度為n、允許前導零的串中數字3出現偶數次的串的數量。但我真正想要的是N位數——首位不能為0。所以必須從dp[n][0]里剔除所有“最高位是0”的串。最高位如果是0把這個0去掉之后剩下的部分就是一個長度為n-1的串。注意去掉最高位的0并不會改變數字3出現的次數。因此“最高位是0且數字3出現偶數次”的串的數量恰好等于dp[n-1][0]。所以答案就是ans dp[n][0] - dp[n-1][0]由于做了取模減法結果可能是負數所以要補一個MOD再取模ans (dp[n][0] - dp[n-1][0] 12345) % 12345;這個“減前一位”的操作其實就是把前導零統一扣掉。理解它比記住公式重要因為很多同類遞推題最后都要做這一步。3.2 完整AC代碼C#include bits/stdc.h using namespace std; const int MOD 12345; int dp[1005][2]; int main() { int n; cin n; // 空串長度為00個3屬于偶數個3 dp[0][0] 1; dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] (dp[i - 1][1] dp[i - 1][0] * 9) % MOD; dp[i][1] (dp[i - 1][0] dp[i - 1][1] * 9) % MOD; } int ans (dp[n][0] - dp[n - 1][0] MOD) % MOD; cout ans endl; return 0; }如果你用的評測環(huán)境不支持#include bits/stdc.h改成#include iostream也一樣。數組開1005是因為N最大到1000dp[0]也要用多開幾個防止下標越界。整個運算過程中dp[i-1]最大不超過12344乘9之后也不到12萬int完全裝得下不需要long long。3.3 用n2、n3驗證代碼把dp表的前幾行展開idp[i][0]dp[i][1]兩數之和0101191102821810037562441000先驗證n2dp[2][0]減dp[1][0]82減9等于73和前面手推完全一致。再驗證n3答案等于756減82674。你也可以自己口算驗證三位數不含3的有8×9×9648個含兩個3的情況分三種討論33X有9個、3Y3有9個、Z33有8個合計648加26等于674。對上號了。這個表里最左邊那列“兩數之和”每一行都是10^i正好是全部長度為i的串的總數。這其實是個非常好的自檢指標如果你代碼算出來的dp[i][0]和dp[i][1]之和不等于10的i次方取模后的值那說明遞推式一定寫錯了。4. 進階矩陣快速冪與數位DP把這道題的價值榨干4.1 N如果變成1e9遞推變矩陣如果題目改一下N給到10的9次方O(N)的遞推也扛不住了。但幸運的是我們的遞推式是線性齊次的可以寫成矩陣形式[ dp[i][0] ] [9 1] [ dp[i-1][0] ] [ dp[i][1] ] [1 9] [ dp[i-1][1] ]初始向量是[1, 0]的轉置對應dp[0][0]1dp[0][1]0。用矩陣快速冪可以在O(log N)時間內算出第N層。核心代碼片段是這樣的struct Mat { int a[2][2]; Mat(bool E false) { memset(a, 0, sizeof(a)); if (E) a[0][0] a[1][1] 1; } Mat operator*(const Mat other) const { Mat c; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) c.a[i][j] (c.a[i][j] a[i][k] * other.a[k][j]) % MOD; return c; } }; Mat power(Mat base, int exp) { Mat res(true); while (exp 0) { if (exp 1) res res * base; base base * base; exp 1; } return res; }使用時構造轉移矩陣M分別算出M的n次方和n-1次方Mat M; M.a[0][0] 9; M.a[0][1] 1; M.a[1][0] 1; M.a[1][1] 9; Mat A power(M, n); Mat B power(M, n - 1); // 初始向量是 [1,0]^T所以取第0行第0列即可 int ans (A.a[0][0] - B.a[0][0] MOD) % MOD;這個版本對原題來說屬于超綱但如果你學到矩陣快速冪再回頭看這道題會發(fā)現它就是最標準的“線性遞推轉矩陣”入門題。4.2 數位DP視角奇偶狀態(tài)的記憶化搜索再換一個角度。如果題目變成“給定L求1到L之間有多少個數含有偶數個3”前面的整體遞推法就用不了了因為這要求統計范圍不是完整的“所有N位數”而是某個任意上界。這時候要用數位DP。數位DP的狀態(tài)里除了常規(guī)的pos當前處理到第幾位、limit是否貼著上界、lead是否還在前導零階段真正描述“3出現次數”的只需要一個0/1變量parity就可以。每遇到一個數字3就把parity異或1其他數字不影響它。int dfs(int pos, int parity, bool limit, bool lead) { if (pos n) return parity 0; if (!limit !lead memo[pos][parity] ! -1) return memo[pos][parity]; int up limit ? s[pos] - 0 : 9; int res 0; for (int d 0; d up; d) { if (lead d 0) res dfs(pos 1, parity, limit d up, true); else res dfs(pos 1, parity ^ (d 3), limit d up, false); } if (!limit !lead) memo[pos][parity] res; return res; }你會看到1313這道題其實是這個模板在L10^N-1時的一個特例因為上界是完整的limit一直為false最后再統一處理前導零扣減。把這道遞推題吃透再去看數位DP會輕松很多。4.3 常見變體清單這類“數字出現次數奇偶性”的題有一大堆變體而且套路高度統一把3換成其他數字k只需要把遞推式里追加數字時的判斷從d3改成dk要求奇數個3最后返回parity1要求至少出現兩次3狀態(tài)要擴展成0沒出現過3、1出現過一次、2出現過兩次及以上不能只用一維奇偶要求統計3出現的總次數而不是個數的奇偶那就不是純計數題遞推式要改成包含“位置權重”的形式思路完全不同。每一道變體本質上都在做同一件事把“3出現的次數”壓縮成盡可能小的狀態(tài)再用轉移來更新它。這個建模思想才是這道題真正值錢的地方。5. 刷題實測中的幾個坑取模、邊界、對拍5.1 取模減法的坑這是最容易踩的坑。公式是dp[n][0]減dp[n-1][0]但兩個數都是取模之后的結果誰大誰小完全不確定。如果dp[n][0]比dp[n-1][0]小直接相減會得到負數而C里負數取模的結果還是負數輸出就WA了。正確做法是加上MOD再取模int ans (dp[n][0] - dp[n - 1][0] MOD) % MOD;因為dp數組的兩個值都在0到12344之間差的最小值是負12344加一次MOD就足夠保證非負。如果以后遇到差可能超過MOD的情況再寫成(x % MOD MOD) % MOD也不遲。5.2 網上兩種邊界的爭議刷題時會發(fā)現網上題解分成兩派寫法初始邊界n1時輸出缺點A寫法dp[1][0]9, dp[1][1]1循環(huán)從2開始需要特判可能輸出9把0也算進一位數概念上不嚴謹B寫法dp[0][0]1, dp[0][1]0循環(huán)從1開始自動得到8需要理解“空串”這個抽象邊界我強烈建議采用B寫法。它不依賴特判而且“先算允許前導零的串再減掉首位0”的思路在全過程中保持一致。如果你在某個OJ上看到答案要求輸出9那多半是題目對“N位數”的定義有額外說明或者評測數據把0算進了一位正整數。但按通常的信息學奧賽題面一位正整數不含0答案就應該是8。5.3 用暴力對拍驗證自己的代碼每次做這種組合計數題我都建議在本地寫一個暴力程序對小數據對拍。Python寫起來最快def dp_ans(n): MOD 12345 even, odd 1, 0 pre_even 0 for i in range(1, n 1): pre_even even ne (odd even * 9) % MOD no (even odd * 9) % MOD even, odd ne, no return (even - pre_even) % MOD def brute(n): cnt 0 for x in range(10 ** (n - 1), 10 ** n): if str(x).count(3) % 2 0: cnt 1 return cnt % 12345 for n in range(1, 7): print(n, dp_ans(n), brute(n), dp_ans(n) brute(n))n1到6足夠覆蓋兩位數、三位數、四位數幾個關鍵邊界。如果全部輸出True你的遞推式基本可以放心交上去。這段腳本我至今還在用碰到類似的遞推題直接改改范圍就能復用。5.4 空間滾動優(yōu)化遞推式里dp[i]只依賴dp[i-1]所以根本不需要開1005×2的二維數組。用兩個變量滾動就行int even 1, odd 0, preEven 0; for (int i 1; i n; i) { preEven even; int ne (odd even * 9) % MOD; int no (even odd * 9) % MOD; even ne; odd no; } cout (even - preEven MOD) % MOD endl;這里的preEven要在更新even之前保存循環(huán)結束后它正好是dp[n-1][0]。滾動數組對這題不是必須的但它體現了遞推題里常見的空間壓縮思維改其他題時經常用到。說實話1313在《信息學奧賽一本通》里算不上難題但它把計數題最重要的兩個概念濃縮在了一起一個是“只關心奇偶性”的狀態(tài)建模另一個是前導零的扣除。我早期做這道題時也在n1輸出8還是9上糾結過后來一直沿用“空串起步、最后減前一位”的寫法整個思路順了很多。如果你正在刷一本通建議做完這題順手把驗證腳本留著后面遇到類似的遞推題直接拿它協助對拍。這道題刷透之后很多“數字出現次數”類的題目你都會覺得格外親切。