lessons/课程/12-历年真题/02-2019至2021容斥函数DAG与区间DP.md

2019–2021 真题：唯一坏对象容斥、函数 DAG 与无歧义区间 DP

本节目标

学习三种把全局约束拆开的办法：多数食材至多一个、函数调用是无环组合、超级括号串有唯一顶层分解。

前置知识与课前自测

前置：计数 DP、容斥、拓扑排序、区间 DP。

1. 一份菜单中能否有两个食材都超过菜数一半？
2. 复合函数中的一次加法最终为何会被后续乘法放大？
3. 文法 DP 若同一字符串有多种推导，会发生什么？

答案

1. 不能，因此坏方案按“唯一多数食材”分类互斥。 2. 执行顺序中其后的所有全局乘法都会乘到这次增量。 3. 会重复计数；必须设计唯一分解状态，而非直接照文法枚举推导树。

问题动机

三题都不能把原过程原样塞进 DP：菜品选择有太多列计数，函数调用会展开成指数长序列，括号段的语法又存在多种看似等价的分割。共同突破口是先找到唯一能造成重复或超限的对象，再改用差值、DAG 系数或无歧义语法状态。

精选例题 1：CSP-S 2019 Emiya 家今天的饭

来源、题意与范围

• 洛谷-P5664 Emiya 家今天的饭
• $n\le100$ 种烹饪方法、$m\le3000$ 种食材；每种方法至多选一道菜，菜单非空，任一食材不超过菜数一半，计数模 998244353。

Hint 1：先忽略食材限制

每种方法选 0 道或任选该行一道，方案数是行选项数乘积。

Hint 2：坏方案怎样分类

违反限制时存在且仅存在一个占严格多数的食材。

Hint 3：固定多数食材 j

每种方法的选择让差值“j 菜数减其他菜数”增加 1、减少 1 或不变。

Observations

• 直接记录每种食材计数维度不可行；“超过一半”只需比较候选食材与其余全部。
• 两个食材不可能同时严格多数，使按食材减坏方案无需更高阶容斥。
• 菜是不同对象，选择某类转移要乘该格菜数或该行其他菜总数。

Editorial 与证明

忽略平衡限制，总方案为各行 (1+rowSum) 乘积减空集。固定食材 j，DP 差值 chosen_j-chosen_other：不选保持，选 j 加一，选其他减一。最终正差值方案恰是 j 超过一半。对所有 j 求和并从总方案减去。

每个坏菜单有唯一多数食材，故被减恰一次；每个好菜单没有正差值食材，不被减。复杂度 $O(mn^2)$，约四千万量级。

核心伪代码与附件

total = product(1 + row_sum[i]) - 1
bad = 0
for ingredient j:
    dp[difference=0] = 1
    for method i:
        choose_none: difference unchanged
        choose j: difference += 1, weight a[i][j]
        choose other: difference -= 1, weight row_sum[i]-a[i][j]
    bad += sum(dp[difference > 0])
answer = total - bad

完整 C++17 附件

精选例题 2：CSP-S 2020 函数调用

来源、题意与范围

• 洛谷-P7077 函数调用
• 数据与函数数至 $10^5$，调用边总数至 $10^6$；函数为单点加、全局乘、按序调用其他函数，调用关系无环。

Hint 1：一个函数的乘法效应

无论内部加了什么，它对进入函数前数组的统一倍率可自底向上求。

Hint 2：加法贡献如何传播

某子调用的加法还会乘上同一调用序列中它后面的所有倍率。

Hint 3：加入超级函数

把最终 Q 次调用也看成一个按序调用函数。

Observations

• 展开调用树会因同一函数被多次引用而指数爆炸；DAG 上应聚合“有效调用系数”。
• 先求每个函数总倍率，再反向扫描调用列表才能知道每个子函数贡献被后缀放大多少。
• 初始数组只需整体乘超级函数倍率；所有单点加按传播系数集中结算。

Editorial

建立 caller 指向 callee 的 DAG，并新增超级函数。逆拓扑计算 mul[f]：加法函数为 1，乘法函数为 v，组合函数为子倍率乘积。正拓扑传播 coef：对每个组合函数从调用列表后向前维护 suffix，向子函数增加 coef[parent]*suffix。最后初始数组乘超级倍率，类型 1 函数在其位置加 coef*f.value。

正确性证明

mul[f] 由复合顺序的乘法结合律正确表示函数对旧数组的线性系数。对某次子调用，它产生的全部加法只受其后调用倍率影响；逆序 suffix 恰为这些倍率乘积。DAG 拓扑保证父系数确定后再传子，汇总所有调用上下文且不展开重复子图。

复杂度 $O(n+m+Q+\sum C)$。

核心伪代码与附件

add super_function calling the query sequence
topo = topological_order(caller -> callee)
for f in reverse(topo): compute mul[f]
coef[super] = 1
for f in topo:
    suffix = 1
    for child in reverse(calls[f]):
        coef[child] += coef[f] * suffix
        suffix *= mul[child]
answer = initial * mul[super]
apply every type-1 addition weighted by coef

完整 C++17 附件

精选例题 3：CSP-S 2021 括号序列

来源、题意与范围

• 洛谷-P7914 括号序列
• $n\le500$，问号替换为括号或星号；按给定三条生成规则计超级括号序列，星号连续段不超过 k。

Hint 1：直接按文法为何危险

规则 AB 可用不同括分重复推导同一串。

Hint 2：唯一分解单位

顶层串可唯一分成若干最外层括号块，块间可为空或一个星号段。

Hint 3：预处理星号段

用 `star[l][r]` 表示该区间能否全替成 1..k 个星号。

Observations

• 目标是替换方案数，不是文法推导数；必须消除文法歧义。
• 每个合法串的第一个最外层括号块结束位置唯一，因此按“第一块”拆分不重。
• 块内部只可能为空、星段、合法串、星段+合法串或合法串+星段；中间 ASB 已包含在内部合法串的顶层分解中。

Editorial

primitive[l][r] 表示单个最外层括号块；valid[l][r] 表示一个或多个块组成的合法串；star[l][r] 表示合法非空星段。另设 after[l][r] 表示从 l 开始的“合法串，或星段后接合法串”，用于 $O(n^3)$ 合并块间可选星段。

正确性证明

最外层括号匹配唯一决定 primitive。任一 valid 的第一 primitive 结束点唯一，其后要么直接接 valid，要么接唯一最大起始星段再接 valid；状态按实际字符边界分解，不按文法括分，故不重。所有生成规则的五类括号内部和两类顶层连接均被转移覆盖，故不漏。

时间 $O(n^3)$，空间 $O(n^2)$。

核心伪代码与附件

star[l][r] = interval can be all '*' and length <= k
for interval length increasing:
    primitive[l][r] = wrap(empty / star / valid / star+valid / valid+star)
    valid[l][r] = primitive[l][r]
                  + sum(first_primitive * after[remaining])
    after[l][r] = valid[l][r] + sum(star_prefix * valid_suffix)

完整 C++17 附件

实现指南

《Emiya》的差值下标要整体平移，每处理一行都要从旧层转移而不得原地更新；《函数调用》要分清“节点的整体乘法系数”和“它被执行多少次”，两次拓扑的方向不同；《括号序列》建议把每个区间状态的语法含义写在数组注释里，先用长度不超过 10 的全串枚举检查是否重复计数。

扩展与联系

三题分别利用“坏对象唯一”“调用图无环”“顶层分解唯一”。计数题开始前要先问：正在数对象，还是在数生成对象的方法？

总结与自检

1. 多数食材为何不需要一般容斥？
2. 函数系数为何从后向前传播？
3. 括号文法的歧义在哪里？
4. 第一 primitive 分解为何唯一？

课后训练建议

对 n 很小分别枚举菜单、展开函数、枚举问号替换做对拍。括号题先写一个判定器，再验证 DP 不是只匹配样例。