---

「IOI2022」数字电路 题解

问题分析

我们有一个树形结构的数字电路：

• 根节点：门 0（阈值门）
• 内部节点：阈值门（0 到 N-1）
• 叶子节点：输入门（N 到 N+M-1）

每个阈值门的状态由其输入中 1 的个数是否达到阈值决定。我们需要支持区间翻转输入门状态，并计算使得根节点输出为 1 的参数赋值方案数。

代码思路解析

这是一个基于组合数学和线段树的优雅解法。

核心数据结构

vector<int> v[N];  // 邻接表存储树结构
int s[N];         // s[x]: 以 x 为根的子树的方案数乘积
int c[N];         // c[y]: 节点 y 在其父节点中的组合系数
int val[i];       // val[i]: 输入门 i 的权重系数
int f[i];         // f[i]: 输入门 i 的当前状态

算法流程

1. 第一次DFS：计算方案数乘积

void dfs1(int x) {
    if (!v[x].size())  // 叶子节点（输入门）
        return (void)(s[x] = 1);
    
    s[x] = v[x].size();  // 初始化为子节点个数
    
    for (int y : v[x])
        dfs1(y), s[x] = 1LL * s[x] * s[y] % mod;
    
    // 计算每个子节点的组合系数
    // 使用前后缀乘积优化
}

关键公式：对于有 $k$ 个子节点的阈值门：

• 总方案数 = $k \times \prod_{i=1}^k s[child_i]$
• 每个子节点的组合系数 = 其他所有兄弟节点方案数的乘积

2. 第二次DFS：计算叶子节点权重

void dfs2(int x, int k) {
    if (!v[x].size())  // 叶子节点
        return (void)(val[x - n] = k);
    
    for (int y : v[x])
        dfs2(y, 1LL * k * c[y] % mod);
}

从根节点向下传递权重系数，最终每个输入门的 val[i] 表示它影响根节点方案数的权重。

3. 线段树维护

struct SgT {
    int sum[N << 2], g[N << 2], tag[N << 2];
    // sum: 区间权重和
    // g: 区间内状态为1的门的权重和
    // tag: 懒标记（翻转）
};

线段树维护所有输入门的：

• sum：区间内所有权重值的和
• g：区间内状态为1的门的权重和

4. 翻转操作

void upd(int x) {
    tag[x] ^= 1, g[x] = (sum[x] - g[x] + mod) % mod;
}

翻转操作就是：g = sum - g（模意义下）

5. 最终答案

return tr.g[1];  // 整个区间的 g 值就是答案

算法正确性证明

这个解法的核心洞察是：

1. 乘法原理：每个阈值门的方案数等于子节点方案数的乘积乘以子节点个数
2. 线性性：根节点的方案数可以表示为输入门状态的线性组合
3. 权重分配：通过两次DFS，为每个输入门分配了正确的权重

最终答案 = $\sum_{i} [f[i] = 1] \times val[i]$

复杂度分析

• 预处理：$O(N + M)$（两次DFS）
• 单次查询：$O(\log M)$（线段树区间翻转）
• 总复杂度：$O(N + M + Q\log M)$

示例验证

对于题目中的例子：

init(3, 4, [-1,0,1,2,1,1,0], [1,0,1,0])

算法会：

1. 构建树结构并计算权重系数
2. 初始化线段树
3. 对于每次翻转操作，快速更新并返回答案

算法标签

• 树形结构处理
• 组合数学
• 线段树

---

总结

这个解法巧妙地利用了组合数学的乘法原理和线性性质，将复杂的阈值逻辑问题转化为简单的权重求和问题。通过两次DFS预处理和线段树动态维护，实现了高效的区间翻转和方案数查询。

关键创新点：

1. 将树形结构的方案数计算转化为线性组合
2. 使用前后缀乘积优化组合系数计算
3. 利用线段树高效支持动态更新

该解法在时间和空间复杂度上都达到了最优，是处理大规模数据的优秀方案。