一、计数 DP 的思维方式
计数题问"有多少种方案"，答案通常巨大（要取模）。核心心法：
状态 = 到目前位置，所有"影响后续合法性"的信息；转移 = 枚举当前这一步放什么
一维不够用就加维：背包问题里"重量"是一维、"体积"又是一维；2025 年真题"员工招聘"里状态达到三维。NOI 大纲 2025 修订版新增"多维动态规划"（6 级），正是这类题的官方背书。
生活类比：统计旅行方案时，你关心的不只是"到了第几天"，还有"花了多少钱、去了几个城市"——每多一个约束条件，账本上就要多记一栏。多维 DP 就是这本多栏账。
取模纪律：所有加法、乘法后立即取模；减法写成
(a - b + mod) % mod；答案最后输出前再确认一次非负。二、容斥原理：正难则反
"至少一个条件被违反"的方案数很难直接数，但"某个指定条件被违反"往往很好数。容斥原理把它们连起来：
|合法方案| = 全部 − Σ|违反条件 i| + Σ|同时违反 i,j| − Σ|同时违反 i,j,k| + …
= ΣS (−1)|S| × "S 中条件全被违反"的方案数
= ΣS (−1)|S| × "S 中条件全被违反"的方案数
经典：P1450 硬币购物
零基础提示 · 完全背包：f[x] = 用若干种硬币（每种无限枚）凑出金额 x 的方案数。递推：依次考虑每种面值 c，
for x = c..上限: f[x] += f[x−c]（正序遍历 = 允许同一枚用多次）。初值 f[0] = 1（"什么都不拿"算一种方案）。这是本页容斥做法的预处理部分。完全背包走查：面值 {1, 2}，金额上限 5
| 阶段 | f[0] | f[1] | f[2] | f[3] | f[4] | f[5] |
|---|---|---|---|---|---|---|
| 初始 | 1 | 0 | 0 | 0 | 0 | 0 |
| 放入面值 1 后 | 1 | 1 | 1 | 1 | 1 | 1 |
| 再放入面值 2 后 | 1 | 1 | 2 | 2 | 3 | 3 |
问题：4 种硬币，面值 ci，第 i 种最多用 di 枚，问凑出金额 s 的方案数（多组询问）。
- 忽略上限：先用完全背包预处理 f[m] = 无限制凑金额 m 的方案数（只做一次）。
- 容斥修正："第 i 种超限" ⇔ 先用掉 di+1 枚，即扣掉金额 (di+1)·ci 后无上限凑剩余：方案数 f[s − (di+1)ci]。
- 枚举超限集合 S（只有 2⁴ = 16 个）：ans = Σ (−1)|S| f[s − Σi∈S(di+1)ci]。
套路提炼：把"有限制"转成"无限制预处理 + 容斥扣减"，是次数/个数带上限类计数题的标准手法。"强制先用 d+1 个"这一步是灵魂——它把"超过上限"变成了可以计算的确定事件。
三、区间计数 DP：防重复计数
计数 DP 最大的坑是同一个方案被多条转移路径重复计算。防重的标准做法是给方案分类，让每类有唯一的生成方式：
- 定义 f[l][r] = 区间 [l,r] 是"两端括号恰好匹配"的合法序列数；g[l][r] = 合法但两端不匹配（即可拆成多段并列）的序列数。
- 并列拼接时规定"最后一段必须是完整匹配段"：g[l][r] = Σ g[l][k]·f[k+1][r]——每个方案按"最后一个匹配段的位置"被唯一计算。
- 转移中枚举 * 段长度时注意题目上限 k，边界取 min。
自检方法：写完计数 DP，拿 n ≤ 5 的小数据暴力枚举所有方案对拍。计数题"看起来对"和"真的对"之间往往隔着一次对拍。
四、多维状态设计实例
| 题目类型 | 状态维度 | 每维的含义 |
|---|---|---|
| 二维费用背包 | f[i][w][v] | 前 i 件、重量 w、体积 v |
| 带次数上限计数 | 容斥 f[m] | 无上限方案 + 16 个子集扣减 |
| 括号序列 | f[l][r] / g[l][r] | 区间 + "两端是否匹配"类别 |
| 员工招聘（2025 T4） | f[i][j][k] | 前 i 人、已录 j 人、某约束计数 k |
设计步骤：① 写下所有限制条件 → ② 每个"影响后续选择"的条件开一维 → ③ 估算状态总数 × 转移代价是否 ≤ 10⁸ → ④ 写转移时确认"不重不漏"。
五、易错点清单
- 容斥符号写反：|S| 为奇数减、偶数加；用
(-1)不如(__builtin_popcount(S) & 1 ? -1 : 1)直观。 - f[s − x] 下标为负时要跳过（贡献为 0），否则会数组越界。
- 多维大数组反复 memset 会 TLE：只清会用到的部分，或用"时间戳"标记代替清零。
- 模意义下除法不能直接做：需要逆元；能避免除法就避免。
六、练习
- P1450【HAOI2008】硬币购物（容斥 + 完全背包预处理）
- P7914 括号序列（区间计数 DP 防重）
- 真题对照：CSP-S 2025 T4 员工招聘（三维 DP 计数，大纲新增"多维 DP"的直接印证）