1. 項(xiàng)目概述與核心思路拆解最近在信奧信息學(xué)奧林匹克的刷題社區(qū)里看到不少朋友在討論P(yáng)11205這道題標(biāo)題是「Cfz Round 9」Hope。這道題本身是一個(gè)典型的組合數(shù)學(xué)與動(dòng)態(tài)規(guī)劃問題但它的描述和背景設(shè)定得挺有意思用“花瓣”和“希望”來包裝讓枯燥的算法題多了一點(diǎn)故事性。我花了些時(shí)間深入研究了一下發(fā)現(xiàn)它核心考察的是對(duì)“子序列和”的計(jì)數(shù)以及取模運(yùn)算的深刻理解非常適合用來鞏固C中的動(dòng)態(tài)規(guī)劃和模運(yùn)算技巧。如果你正在準(zhǔn)備信奧或者想提升自己的算法思維這道題是一個(gè)不錯(cuò)的練手材料。簡(jiǎn)單來說題目是這樣的你有n堆花瓣每堆有a_i片。你可以從這些堆中任意選擇若干堆可以不選也可以全選然后從你選擇的每一堆中再任意拿出任意數(shù)量的花瓣最少1片最多拿光該堆。你的目標(biāo)是讓你最終拿出的花瓣總數(shù)是偶數(shù)。題目要求計(jì)算有多少種不同的選擇方案結(jié)果需要對(duì)一個(gè)大質(zhì)數(shù)通常是1e97取模。初看可能覺得就是枚舉所有子集然后判斷和是否為偶數(shù)但n的范圍如果很大比如10^52^n的枚舉顯然會(huì)超時(shí)。所以這題的核心在于利用數(shù)學(xué)性質(zhì)將指數(shù)級(jí)復(fù)雜度降為線性。它考驗(yàn)的是你能否跳出“暴力枚舉”的思維定式轉(zhuǎn)而從“奇偶性”這個(gè)關(guān)鍵屬性入手找到計(jì)數(shù)問題的遞推關(guān)系。接下來我會(huì)詳細(xì)拆解這道題的解題思路、C實(shí)現(xiàn)細(xì)節(jié)以及一些在編碼和調(diào)試中容易踩的坑。2. 問題本質(zhì)與數(shù)學(xué)模型建立2.1 從“花瓣”到“二進(jìn)制”理解問題本質(zhì)首先我們需要把那個(gè)浪漫的“花瓣”故事翻譯成嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型。設(shè)總共有n堆花瓣第i堆的數(shù)量為a_i。我們的一個(gè)“操作”分為兩步選擇一個(gè)堆的集合SS是{1, 2, ..., n}的一個(gè)子集。對(duì)于集合S中的每一個(gè)堆i決定從中拿出多少片花瓣記作x_i其中1 ≤ x_i ≤ a_i。那么一次完整的操作帶來的“花瓣總數(shù)”就是 sum_{i in S} x_i。題目要求這個(gè)總和是偶數(shù)。一種常見的錯(cuò)誤思路是分別考慮“選擇哪些堆”和“每堆拿多少”然后試圖將方案數(shù)相乘。這是因?yàn)閷?duì)于一堆被選中的花瓣你拿出花瓣的方案數(shù)就是a_i種拿1片、2片...a_i片。如果僅僅要求總和滿足某個(gè)條件那么“選擇堆”和“每堆拿多少”這兩個(gè)決策是相互耦合的不能獨(dú)立計(jì)算。正確的突破口在于奇偶性。一個(gè)整數(shù)是偶數(shù)當(dāng)且僅當(dāng)它除以2的余數(shù)為0。而多個(gè)數(shù)相加的和的奇偶性只與每個(gè)加數(shù)自身的奇偶性有關(guān)。具體來說偶數(shù) 偶數(shù) 偶數(shù)偶數(shù) 奇數(shù) 奇數(shù)奇數(shù) 奇數(shù) 偶數(shù)這意味著當(dāng)我們考慮總和sum的奇偶性時(shí)x_i的具體值比如是3還是5并不重要重要的是x_i本身是奇數(shù)還是偶數(shù)。對(duì)于第i堆它有a_i片花瓣那么從中拿出花瓣x_i的可能取值是1, 2, ..., a_i。在這些取值中有多少個(gè)是奇數(shù)有多少個(gè)是偶數(shù)如果a_i是奇數(shù)比如a_i5那么可能的x_i是: 1(奇), 2(偶), 3(奇), 4(偶), 5(奇)。奇數(shù)的個(gè)數(shù)是3偶數(shù)的個(gè)數(shù)是2。如果a_i是偶數(shù)比如a_i4那么可能的x_i是: 1(奇), 2(偶), 3(奇), 4(偶)。奇數(shù)的個(gè)數(shù)是2偶數(shù)的個(gè)數(shù)是2。我們可以總結(jié)出一個(gè)公式設(shè)odd[i]為從第i堆中能拿出奇數(shù)片花瓣的方案數(shù)。設(shè)even[i]為從第i堆中能拿出偶數(shù)片花瓣的方案數(shù)注意這里“拿出0片”不算一種方案因?yàn)轭}目要求從選中的堆里至少拿1片。那么如果a_i是奇數(shù)odd[i] (a_i 1) / 2,even[i] a_i / 2。如果a_i是偶數(shù)odd[i] a_i / 2,even[i] a_i / 2。注意這里even[i]包含了x_i為偶數(shù)的情況但x_i至少為2。當(dāng)a_i1時(shí)它只能是奇數(shù)even[i]0。我們的公式也兼容這種情況。現(xiàn)在問題轉(zhuǎn)化了我們有n個(gè)“位置”對(duì)應(yīng)n堆花瓣。對(duì)于每個(gè)位置i我們有兩種“狀態(tài)”選擇讓從這一堆拿出的花瓣數(shù)x_i為奇數(shù)有odd[i]種具體實(shí)現(xiàn)方式或者為偶數(shù)有even[i]種具體實(shí)現(xiàn)方式。我們需要選擇一條“路徑”使得所有被選中狀態(tài)即我們決定從這一堆拿花瓣的x_i之和為偶數(shù)。但這里還有一個(gè)維度我們可以不選某一堆。不選這一堆意味著我們既沒有采用“奇數(shù)”狀態(tài)也沒有采用“偶數(shù)”狀態(tài)。為了統(tǒng)一處理我們可以把“不選”視為第三種狀態(tài)它對(duì)總和的貢獻(xiàn)為00是偶數(shù)。但是這樣處理動(dòng)態(tài)規(guī)劃時(shí)會(huì)稍微復(fù)雜。更優(yōu)雅的處理方式是使用動(dòng)態(tài)規(guī)劃定義dp[i][0]和dp[i][1]。2.2 動(dòng)態(tài)規(guī)劃狀態(tài)定義與轉(zhuǎn)移方程定義dp[i][0]: 考慮前i堆花瓣選出若干堆并決定拿法使得拿出的花瓣總數(shù)為偶數(shù)的方案總數(shù)。dp[i][1]: 考慮前i堆花瓣選出若干堆并決定拿法使得拿出的花瓣總數(shù)為奇數(shù)的方案總數(shù)。這里的關(guān)鍵是“選出若干堆”已經(jīng)包含了“不選”的情況。我們?nèi)绾螐膁p[i-1]轉(zhuǎn)移到dp[i]呢當(dāng)我們考慮第i堆時(shí)我們有三種選擇不選第i堆那么前i堆的總和奇偶性就和前i-1堆一樣。所以dp[i][0]和dp[i][1]都會(huì)繼承dp[i-1][0]和dp[i-1][1]的方案。選第i堆且拿出奇數(shù)片花瓣這會(huì)對(duì)總和奇偶性產(chǎn)生影響。如果前i-1堆的總和是偶數(shù)加上一個(gè)奇數(shù)總和變成奇數(shù)。如果前i-1堆的總和是奇數(shù)加上一個(gè)奇數(shù)總和變成偶數(shù)。并且這種選擇有odd[i]種具體的實(shí)現(xiàn)方式。選第i堆且拿出偶數(shù)片花瓣這不會(huì)改變總和的奇偶性。如果前i-1堆的總和是偶數(shù)加上一個(gè)偶數(shù)總和仍是偶數(shù)。如果前i-1堆的總和是奇數(shù)加上一個(gè)偶數(shù)總和仍是奇數(shù)。這種選擇有even[i]種具體的實(shí)現(xiàn)方式。因此我們可以得到狀態(tài)轉(zhuǎn)移方程對(duì)于dp[i][0]前i堆總和為偶數(shù)它可以從以下幾種情況轉(zhuǎn)移而來情況A不選第i堆且前i-1堆總和已經(jīng)是偶數(shù)。方案數(shù) dp[i-1][0]。情況B選第i堆拿出偶數(shù)片花瓣且前i-1堆總和是偶數(shù)。方案數(shù) dp[i-1][0] * even[i]。情況C選第i堆拿出奇數(shù)片花瓣且前i-1堆總和是奇數(shù)。方案數(shù) dp[i-1][1] * odd[i]。所以dp[i][0] dp[i-1][0] dp[i-1][0] * even[i] dp[i-1][1] * odd[i]。 化簡(jiǎn)一下dp[i][0] dp[i-1][0] * (1 even[i]) dp[i-1][1] * odd[i]。同理對(duì)于dp[i][1]前i堆總和為奇數(shù)情況D不選第i堆且前i-1堆總和是奇數(shù)。方案數(shù) dp[i-1][1]。情況E選第i堆拿出偶數(shù)片花瓣且前i-1堆總和是奇數(shù)。方案數(shù) dp[i-1][1] * even[i]。情況F選第i堆拿出奇數(shù)片花瓣且前i-1堆總和是偶數(shù)。方案數(shù) dp[i-1][0] * odd[i]。所以dp[i][1] dp[i-1][1] dp[i-1][1] * even[i] dp[i-1][0] * odd[i]。 化簡(jiǎn)一下dp[i][1] dp[i-1][1] * (1 even[i]) dp[i-1][0] * odd[i]。初始狀態(tài)是什么考慮前0堆即一堆都沒有。此時(shí)我們“什么也沒選”花瓣總和為0是偶數(shù)。所以dp[0][0] 1一種方案空集dp[0][1] 0。最終我們要求的答案就是dp[n][0]。但是這里有一個(gè)小陷阱dp[n][0]包含了“所有堆都不選”這種方案即空集此時(shí)總和為0偶數(shù)。題目是否允許“所有堆都不選”仔細(xì)讀題“你可以選擇若干堆花瓣”“若干”在中文競(jìng)賽語境中通常包括0即不選。所以空集是合法的答案就是dp[n][0]。2.3 邊界情況與取模運(yùn)算在計(jì)算odd[i]和even[i]時(shí)我們直接用了除法。在C中整數(shù)除法是向下取整。我們的公式odd[i] (a_i 1) / 2(當(dāng)a_i為奇數(shù))even[i] a_i / 2(當(dāng)a_i為奇數(shù))odd[i] a_i / 2(當(dāng)a_i為偶數(shù))even[i] a_i / 2(當(dāng)a_i為偶數(shù))可以用一個(gè)條件判斷或者更巧妙的位運(yùn)算來實(shí)現(xiàn)long long odd (a 1) / 2; long long even a / 2;無論a是奇是偶(a1)/2恰好就是奇數(shù)方案數(shù)a/2恰好就是偶數(shù)方案數(shù)。你可以用a4和a5驗(yàn)證一下。另一個(gè)重點(diǎn)是取模。題目結(jié)果通常對(duì)MOD 1e97取模。在動(dòng)態(tài)規(guī)劃轉(zhuǎn)移過程中所有的加法和乘法都可能產(chǎn)生非常大的中間結(jié)果必須在每一步運(yùn)算后及時(shí)取模防止溢出。特別是dp[i-1][0] * even[i]這種乘法兩個(gè)數(shù)都可能接近1e9乘積會(huì)超過64位整數(shù)范圍。所以我們需要在乘法后立即取模。C中我們可以定義const int MOD 1e9 7;然后寫一個(gè)安全的加法取模和乘法取模函數(shù)或者直接使用((a % MOD) * (b % MOD)) % MOD這樣的寫法。由于我們使用long long類型可以承受兩次1e97范圍內(nèi)的數(shù)相乘結(jié)果約1e18在64位整數(shù)范圍內(nèi)所以直接乘再取模是安全的。3. C代碼實(shí)現(xiàn)與逐行解析理解了動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程代碼實(shí)現(xiàn)就相對(duì)直接了。但其中有一些細(xì)節(jié)和優(yōu)化技巧值得注意。3.1 基礎(chǔ)版本實(shí)現(xiàn)我們先給出一個(gè)最直觀的實(shí)現(xiàn)使用二維數(shù)組dp[n1][2]。#include iostream #include vector using namespace std; const int MOD 1e9 7; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } // dp[i][0]: 偶數(shù)和方案數(shù), dp[i][1]: 奇數(shù)和方案數(shù) vectorvectorlong long dp(n 1, vectorlong long(2, 0)); dp[0][0] 1; // 前0堆空集和為0偶數(shù) dp[0][1] 0; for (int i 1; i n; i) { long long ai a[i-1]; long long odd (ai 1) / 2; // 拿出奇數(shù)片的方案數(shù) long long even ai / 2; // 拿出偶數(shù)片的方案數(shù) // 計(jì)算 dp[i][0] dp[i][0] (dp[i-1][0] * (1 even)) % MOD; dp[i][0] (dp[i][0] dp[i-1][1] * odd) % MOD; // 計(jì)算 dp[i][1] dp[i][1] (dp[i-1][1] * (1 even)) % MOD; dp[i][1] (dp[i][1] dp[i-1][0] * odd) % MOD; } cout dp[n][0] endl; return 0; }代碼解析輸入處理讀入n和數(shù)組a。DP數(shù)組初始化創(chuàng)建dp[n1][2]并初始化dp[0][0]1dp[0][1]0。核心循環(huán)i從1遍歷到n對(duì)應(yīng)考慮前i堆。ai a[i-1]因?yàn)槲覀兊腶數(shù)組下標(biāo)從0開始。計(jì)算odd和even。根據(jù)轉(zhuǎn)移方程更新dp[i][0]和dp[i][1]。注意這里(1 even)對(duì)應(yīng)了“不選”方案數(shù)1和“選且拿偶數(shù)片”方案數(shù)even這兩種情況的和。每一步運(yùn)算后都立即取模。輸出最終答案dp[n][0]。這個(gè)代碼的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度是O(n)對(duì)于n最大為10^5的情況完全足夠。3.2 空間優(yōu)化滾動(dòng)數(shù)組注意到dp[i]只依賴于dp[i-1]我們可以用滾動(dòng)數(shù)組將空間復(fù)雜度優(yōu)化到O(1)。這是競(jìng)賽中常見的優(yōu)化技巧。#include iostream #include vector using namespace std; const int MOD 1e9 7; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } long long dp_even 1; // 對(duì)應(yīng) dp[0][0] long long dp_odd 0; // 對(duì)應(yīng) dp[0][1] for (int i 0; i n; i) { long long ai a[i]; long long odd (ai 1) / 2; long long even ai / 2; // 保存舊值因?yàn)橛?jì)算新的dp_even需要舊的dp_odd long long old_even dp_even; long long old_odd dp_odd; // 計(jì)算新的dp_even dp_even (old_even * (1 even)) % MOD; dp_even (dp_even old_odd * odd) % MOD; // 計(jì)算新的dp_odd dp_odd (old_odd * (1 even)) % MOD; dp_odd (dp_odd old_even * odd) % MOD; } cout dp_even endl; return 0; }優(yōu)化點(diǎn)說明我們只維護(hù)兩個(gè)變量dp_even和dp_odd分別代表考慮完當(dāng)前堆之后總和為偶數(shù)和奇數(shù)的方案數(shù)。在每次循環(huán)開始時(shí)必須用old_even和old_odd保存上一輪的值。因?yàn)橛?jì)算新的dp_even時(shí)公式里需要用到舊的dp_odd。如果先更新dp_even再更新dp_odd時(shí)用的dp_even就已經(jīng)是新的了會(huì)導(dǎo)致錯(cuò)誤。這個(gè)版本更節(jié)省內(nèi)存在實(shí)際運(yùn)行中也可能因更好的緩存局部性而稍快一些。3.3 使用位運(yùn)算與更簡(jiǎn)潔的寫法我們可以利用整數(shù)除法的特性以及C中l(wèi)ong long的類型安全寫出更簡(jiǎn)潔的代碼。同時(shí)對(duì)于(1 even)這個(gè)表達(dá)式我們可以直接計(jì)算(even 1) % MOD但注意even可能已經(jīng)很大所以先取模再加。#include bits/stdc.h // 競(jìng)賽常用頭文件包含大多數(shù)標(biāo)準(zhǔn)庫(kù) using namespace std; const int MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 這兩行用于加速C的輸入輸出流 int n; cin n; long long even_cnt 1, odd_cnt 0; // even_cnt: 偶數(shù)和的方案數(shù) for (int i 0; i n; i) { long long a; cin a; long long odd (a 1) / 2 % MOD; // 拿出奇數(shù)片的方案數(shù)先取模防止后面乘法溢出 long long even a / 2 % MOD; // 拿出偶數(shù)片的方案數(shù) long long new_even (even_cnt * (even 1) % MOD odd_cnt * odd % MOD) % MOD; long long new_odd (odd_cnt * (even 1) % MOD even_cnt * odd % MOD) % MOD; even_cnt new_even; odd_cnt new_odd; } cout even_cnt endl; return 0; }代碼技巧與注意事項(xiàng)#include bits/stdc.h這是一個(gè)GCC編譯器特有的萬能頭文件包含了競(jìng)賽中常用的幾乎所有標(biāo)準(zhǔn)庫(kù)組件。在信奧等競(jìng)賽環(huán)境中通常允許使用可以節(jié)省寫一堆#include的時(shí)間。但在生產(chǎn)代碼或某些嚴(yán)格環(huán)境中不建議使用。ios::sync_with_stdio(false); cin.tie(nullptr);這是C中關(guān)閉C風(fēng)格輸入輸出流與C流的同步并解綁cin和cout的語句。可以大幅提升大量數(shù)據(jù)輸入輸出的速度。在輸入數(shù)據(jù)量很大比如n10^5時(shí)效果明顯。在計(jì)算odd和even時(shí)我們直接對(duì)MOD取模。這是因?yàn)楹罄m(xù)的乘法even_cnt * (even 1)中even_cnt可能已經(jīng)是一個(gè)模MOD后的值在0到MOD-1之間而(even1)如果是一個(gè)很大的數(shù)接近a_i直接相乘可能導(dǎo)致64位溢出(1e97) * (1e9)約等于 1e18仍在long long范圍內(nèi)但為了安全習(xí)慣先取模。更嚴(yán)謹(jǐn)?shù)膶懛ㄊ?(a1)/2) % MOD因?yàn)?a1)/2最大約為5e8小于MOD所以這里不取模其實(shí)也是安全的。但先取模是個(gè)好習(xí)慣。轉(zhuǎn)移方程寫在一行內(nèi)清晰且避免了臨時(shí)變量。注意每個(gè)乘法后都跟了% MOD加法后也跟了% MOD確保中間結(jié)果不會(huì)溢出。4. 算法正確性驗(yàn)證與測(cè)試用例設(shè)計(jì)寫完代碼不代表萬事大吉必須用多種測(cè)試用例驗(yàn)證其正確性。對(duì)于動(dòng)態(tài)規(guī)劃問題我們可以從小規(guī)模數(shù)據(jù)開始手動(dòng)計(jì)算或暴力枚舉來驗(yàn)證。4.1 暴力枚舉驗(yàn)證程序我們可以寫一個(gè)簡(jiǎn)單的暴力程序用于驗(yàn)證n較小比如n 10時(shí)動(dòng)態(tài)規(guī)劃程序的結(jié)果是否正確。暴力法的思路是枚舉所有堆的選擇情況2^n種對(duì)于每一種選擇再枚舉每一堆拿多少片如果選了該堆則有a_i種拿法計(jì)算總和為偶數(shù)的方案數(shù)。// 暴力驗(yàn)證程序 (僅用于小數(shù)據(jù)驗(yàn)證) #include iostream #include vector using namespace std; long long brute_force(const vectorint a) { int n a.size(); long long total 0; // 枚舉所有堆的選擇狀態(tài)用mask表示 for (int mask 0; mask (1 n); mask) { long long ways_for_mask 1; // 對(duì)于當(dāng)前選擇狀態(tài)mask計(jì)算所有可能的拿法方案數(shù) for (int i 0; i n; i) { if (mask (1 i)) { // 如果第i堆被選中 ways_for_mask * a[i]; // 對(duì)于選中的堆有a[i]種拿法 } // 注意如果沒選中則只有1種方式即不參與貢獻(xiàn)所以乘1可以省略 } // 但是我們這里計(jì)算的是所有選擇下的總方案數(shù)沒有區(qū)分奇偶。 // 我們需要的是總和為偶數(shù)的方案數(shù)暴力法需要更精細(xì)的枚舉。 // 因此上面的暴力法是不完整的。正確的暴力法需要遞歸枚舉每堆拿多少片。 } return total; }完整的暴力枚舉遞歸寫法更復(fù)雜但對(duì)于n5a_i3的情況是可行的。我們可以用這樣的數(shù)據(jù)測(cè)試n1, a[1]。方案選這堆拿1片奇無效。不選和0偶有效。答案應(yīng)為1。n1, a[2]。方案不選(1種)。選且拿1片(奇無效)。選且拿2片(偶有效)。答案應(yīng)為2。n2, a[1,1]。我們可以手動(dòng)枚舉所有選擇拿法組合驗(yàn)證DP程序輸出。4.2 設(shè)計(jì)測(cè)試用例一個(gè)好的測(cè)試集應(yīng)該包含以下情況最小輸入n0如果題目允許但通常n1。n1a_i為奇數(shù)和偶數(shù)。小規(guī)模隨機(jī)數(shù)據(jù)n5, a_i在1到5之間用暴力程序驗(yàn)證。邊界值a_i1只有奇數(shù)方案a_i10^9大數(shù)測(cè)試取模。全奇數(shù)/全偶數(shù)所有a_i都是奇數(shù)或都是偶數(shù)觀察規(guī)律。大nn10^5a_i隨機(jī)或全為1測(cè)試程序性能和是否溢出。例如我們可以設(shè)計(jì)以下測(cè)試輸入1 1 2 輸出12 輸入2 2 1 1 輸出23 解釋堆1有1片(只能拿1奇)堆2有1片(只能拿1奇)。 方案都不選(1種)只選1(1種)只選2(1種)選1和2(1*11種和112偶)。共4種等等我們算一下。 - 都不選和0(偶) - 1種 - 只選堆1拿1片和1(奇) - 無效 - 只選堆2拿1片和1(奇) - 無效 - 選堆1和堆2堆1拿1堆2拿1和2(偶) - 1種 總有效方案 1 0 0 1 2種。 我們的DP程序會(huì)輸出2嗎我們來模擬一下。 a[1,1], odd11, even10; odd21, even20. 初始: dp_even1, dp_odd0. i0 (a1): new_even 1*(01) 0*1 1 new_odd 0*(01) 1*1 1 dp_even1, dp_odd1 i1 (a1): new_even 1*(01) 1*1 112 new_odd 1*(01) 1*1 112 dp_even2, dp_odd2 輸出dp_even2。正確。 輸入3 3 2 2 2 輸出326 我們可以手動(dòng)計(jì)算或?qū)憘€(gè)暴力程序驗(yàn)證。4.3 對(duì)拍測(cè)試在競(jìng)賽準(zhǔn)備中對(duì)于一道題可以寫一個(gè)保證正確的暴力程序僅用于小數(shù)據(jù)和一個(gè)高效的DP程序然后隨機(jī)生成小數(shù)據(jù)比較兩者的輸出是否一致。這個(gè)過程叫做“對(duì)拍”。這是驗(yàn)證算法正確性的非常有效的方法。5. 常見錯(cuò)誤與調(diào)試技巧即使思路正確實(shí)現(xiàn)時(shí)也容易遇到各種問題。下面總結(jié)幾個(gè)常見的坑。5.1 整數(shù)溢出這是最普遍的問題。即使使用了long long在乘法dp_even * (even 1)時(shí)如果dp_even和(even1)都在1e9量級(jí)乘積約為1e18這剛好在long long的最大值(約9e18)以內(nèi)所以是安全的。但是如果你在乘法之前沒有取模而dp_even是已經(jīng)取過模的數(shù)小于1e97even1也小于1e97乘積小于1e18安全。然而更安全且好的習(xí)慣是在每一次加法和乘法運(yùn)算后都立即取模尤其是當(dāng)模數(shù)不是1e97而是其他數(shù)或者中間結(jié)果可能累加得很大時(shí)。錯(cuò)誤示例dp_even (dp_even * (even 1) dp_odd * odd) % MOD; // 可能溢出如果dp_even * (even 1)先計(jì)算結(jié)果可能超過long long范圍盡管本題不太可能導(dǎo)致溢出為負(fù)數(shù)然后取模得到錯(cuò)誤結(jié)果。穩(wěn)妥寫法是dp_even (dp_even * ((even 1) % MOD) % MOD dp_odd * (odd % MOD) % MOD) % MOD;或者分步取模long long t1 dp_even * ((even 1) % MOD) % MOD; long long t2 dp_odd * (odd % MOD) % MOD; dp_even (t1 t2) % MOD;5.2 初始狀態(tài)設(shè)置錯(cuò)誤dp[0][0]應(yīng)該等于1空集方案還是等于0這取決于對(duì)“前0堆”的理解。如果認(rèn)為沒有堆時(shí)只有一種選擇什么都不選其和為0偶數(shù)那么dp[0][0]1。如果認(rèn)為必須至少選一堆那初始狀態(tài)就不同了。根據(jù)題目描述“可以選擇若干堆”“若干”包括0所以初始狀態(tài)設(shè)為1是正確的。我們可以通過一個(gè)簡(jiǎn)單例子驗(yàn)證n0如果允許答案應(yīng)該是1空集。我們的程序如果dp[0][0]1那么輸出就是1。如果dp[0][0]0輸出就是0顯然是錯(cuò)的。5.3 轉(zhuǎn)移方程系數(shù)錯(cuò)誤最容易出錯(cuò)的是(1 even)這個(gè)系數(shù)。它代表了對(duì)于當(dāng)前堆不選和選且拿偶數(shù)片這兩種決策的總方案數(shù)。不選有1種方式選且拿偶數(shù)片有even種方式。所以是1even。有些人可能會(huì)寫成even漏掉了“不選”的1。另一個(gè)易錯(cuò)點(diǎn)是odd和even的計(jì)算公式。一定要用(a1)/2和a/2并且注意整數(shù)除法。可以用幾個(gè)例子驗(yàn)證a1: odd(11)/21, even1/20。正確只能拿1片是奇數(shù)。a2: odd(21)/21, even2/21。正確可以拿1(奇)或2(偶)。a3: odd(31)/22, even3/21。正確可以拿1,3(奇)或2(偶)。5.4 取模減法出現(xiàn)負(fù)數(shù)在動(dòng)態(tài)規(guī)劃中我們通常只有加法和乘法。但有些類似的題目可能會(huì)涉及減法。在模運(yùn)算中減法可能導(dǎo)致負(fù)數(shù)。正確的處理方式是(a - b MOD) % MOD。5.5 輸入輸出效率當(dāng)n很大10^5時(shí)使用cin/cout可能會(huì)比較慢。雖然我們用了ios::sync_with_stdio(false); cin.tie(nullptr);來加速但在極端情況下使用C的scanf/printf可能更穩(wěn)。不過對(duì)于信奧比賽通常這個(gè)優(yōu)化已經(jīng)足夠。6. 算法擴(kuò)展與思維提升解決了這道題我們可以思考一些相關(guān)的變種問題這有助于深化對(duì)這類計(jì)數(shù)問題的理解。6.1 如果要求總和是奇數(shù)怎么辦很簡(jiǎn)單答案就是dp[n][1]。動(dòng)態(tài)規(guī)劃過程完全一樣只是最后輸出不同的狀態(tài)。6.2 如果要求總和是3的倍數(shù)怎么辦這時(shí)奇偶性不夠用了我們需要將狀態(tài)擴(kuò)展為模3的余數(shù)dp[i][0],dp[i][1],dp[i][2]分別表示前i堆總和模3余0、1、2的方案數(shù)。對(duì)于第i堆我們拿出k片花瓣1 ≤ k ≤ a_i。k模3的余數(shù)可以是0,1,2。我們需要計(jì)算cnt0[i],cnt1[i],cnt2[i]分別表示從第i堆中能拿出花瓣數(shù)模3余0、1、2的方案數(shù)。計(jì)算這個(gè)需要一點(diǎn)技巧需要根據(jù)a_i除以3的余數(shù)來分類討論。轉(zhuǎn)移方程也會(huì)變得更復(fù)雜一些但思路一致dp[i][new_r] sum_{old_r} dp[i-1][old_r] * cnt[(new_r - old_r 3) % 3][i]。這里cnt[r][i]表示從第i堆中拿出花瓣數(shù)模3余r的方案數(shù)。6.3 如果每堆可以不拿即拿0片但至少選一堆呢題目原意是“在你選擇的每一堆花瓣中拿出任意數(shù)量的花瓣”這個(gè)“任意數(shù)量”是否包括0通常理解為至少拿1片因?yàn)槿绻试S拿0片那么“選擇”這堆就沒有意義了它等同于不選。但如果我們修改條件允許拿0片那么even[i]就需要重新計(jì)算因?yàn)閤_i0是偶數(shù)也是一種方案。此時(shí)even[i] a_i / 2 1如果a_i是偶數(shù)需要仔細(xì)分析。同時(shí)“至少選一堆”意味著最終答案不能包含“所有堆都不選”的空集方案。我們可以在最后輸出時(shí)減去1即空集方案或者調(diào)整初始狀態(tài)dp[0][0]0并在轉(zhuǎn)移中體現(xiàn)“至少選一堆”的限制這會(huì)更復(fù)雜。6.4 更一般的模M計(jì)數(shù)如果要求總和模M等于一個(gè)特定的數(shù)r那么狀態(tài)就是dp[i][rem]表示前i堆總和模M余rem的方案數(shù)。對(duì)于每一堆我們需要預(yù)處理一個(gè)數(shù)組cnt[0..M-1]表示從該堆中能拿出的花瓣數(shù)模M余0,1,...,M-1的方案數(shù)。這個(gè)預(yù)處理可以通過計(jì)算a_i除以M的商和余數(shù)來批量完成。轉(zhuǎn)移方程為dp[i][new_rem] sum_{old_rem0}^{M-1} dp[i-1][old_rem] * cnt[(new_rem - old_rem M) % M]。 時(shí)間復(fù)雜度為O(n * M^2)如果M不大比如幾十是可以接受的。如果M很大就需要更高效的數(shù)學(xué)方法比如使用生成函數(shù)或FFT快速傅里葉變換但這已經(jīng)超出了信奧初賽的范圍。通過這道P11205 “Hope”的深入剖析我們不僅學(xué)會(huì)了一個(gè)具體的動(dòng)態(tài)規(guī)劃解法更重要的是掌握了將組合計(jì)數(shù)問題轉(zhuǎn)化為基于模運(yùn)算的狀態(tài)機(jī)DP的通用思路。在面對(duì)“方案數(shù)取模”類問題時(shí)多思考“奇偶性”、“模M余數(shù)”這些不變量往往能化繁為簡(jiǎn)從指數(shù)枚舉降到線性復(fù)雜度。在代碼實(shí)現(xiàn)上牢記取模運(yùn)算的細(xì)節(jié)善用滾動(dòng)數(shù)組優(yōu)化空間并通過小數(shù)據(jù)對(duì)拍來驗(yàn)證正確性這些都是信奧競(jìng)賽中必備的實(shí)戰(zhàn)技能。