数学、数论与组合 · HTML
数学 / 逻辑形态
独立阶段相乘；无序选 k 个为 C(n,k)；重叠性质用 |A∪B|=Σ单集-Σ交集+… 修正。
识别信号
- 只需方案数而非列出方案
- 对象可按角色或位置分组
- 顺序是否重要可明确区分
- 存在重复计数需除去或容斥
- 约束可转成选集合
容易误判的相似信号
| Signal | Why it is different |
|---|
| 选择之间强依赖 | 若局部选择改变未来状态，通常需 DP 而非简单组合式。 |
| 对象不可区分却套排列 | 必须先明确标号、重复与顺序语义。 |
核心不变量
每个合法对象映射到唯一计数表示，或明确知道其被计数的固定次数并校正。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 类别规模、剩余选择数、组合数表或阶乘/逆阶乘，以及容斥子集。 |
| Transition | 按独立阶段乘、按互斥情况加；有交叠时对子集交集按奇偶符号修正。 |
| Frontier / order | 已处理类别已被汇总成计数；未处理类别只通过剩余参数影响。 |
Python 骨架
def binomial_table(n):
c = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
c[i][0] = c[i][i] = 1
for k in range(1, i):
c[i][k] = c[i-1][k-1] + c[i-1][k]
return c
def inclusion_exclusion(universe_size, bad_intersections):
# map nonempty subset mask -> size of intersection of those bad sets
good = universe_size
for mask, size in bad_intersections.items():
bits = mask.bit_count()
good += (-1 if bits % 2 else 1) * size
return good
正确性思路
- Pascal 递推按是否选择某指定对象分成两个互斥且完备的情况。
- 乘法原理为每条完整方案建立唯一阶段选择元组。
- 容斥中含 k 个坏性质的对象贡献 Σ(-1)^j C(k,j)=0，从坏并集中消去。
- 不含坏性质的对象只保留初始一次贡献。
复杂度
| Time | Space | Parameters |
|---|
| 组合表 O(n²)；k 个性质的容斥 O(2^k) | O(n²) 或滚动 O(n) | n 为对象规模，k 为容斥性质数 |
边界条件
- C(n,0)=C(n,n)=1
- k<0 或 k>n 时为 0
- 空乘积为 1
- 顺序是否重要必须先确定
- 模数下除法需逆元条件
错误模式
| Pattern | Why it fails / fix |
|---|
| 排列组合混淆 | 先问交换两个被选对象是否产生新方案。 |
| 交叠情况直接相加 | 重叠对象会重复计数，需要容斥。 |
| 过早整除取模 | 模运算中的除法不能当普通整数除法。 |
选择与排除规则
- 只计数且结构独立：先找乘法/加法原理。
- 无序选子集：组合数；有序安排：排列。
- 性质少但重叠复杂：容斥。
- 选择影响未来且状态有限：动态规划。
相关模板
| Relation | Template | Boundary |
|---|
| alternative | 数位 DP | 没有紧上界或性质可直接组合计数。 |
| 枚举替代 | 子集 / 组合回溯 | 需要输出具体方案 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | C(5,2)×3=30 种。 |
| Scenario | 从 5 种茶中无序选 2 种，再从 3 种杯中选 1 个。 |
| Walkthrough | 茶的顺序不产生新选择；杯子阶段与茶选择独立，因此相乘。 |
Recall prompts
我的补充