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