题解：推理链的传递闭包与逻辑推导

---

问题分析

本题要求根据已知发生的事件和推理规则（$A \rightarrow B$），找出所有必然发生的事件。关键点：

• 推理规则形成有向无环图（DAG）
• $A \rightarrow B$ 表示 $A$ 发生则 $B$ 必然发生，但 $A$ 不发生时不保证 $B$ 不发生
• 需要找出所有逻辑上必然发生的事件

补充说明：对于事件 $X$，如果有多个前驱 $Y_1 \rightarrow X, Y_2 \rightarrow X, \dots$，那么 $X$ 发生当且仅当至少有一个 $Y_i$ 发生。

---

算法核心思想

1. 传递闭包

首先计算每个事件能推出哪些事件。设 $f[x][y] = 1$ 表示从 $x$ 出发（通过一系列推理）可以推出 $y$ 发生。

由于图是 DAG，可以通过 DFS 或拓扑排序计算：

$$f[x] = \{x\} \cup \bigcup_{y \in \text{后继}(x)} f[y] $$

2. 反向逻辑推导

对于事件 $x$，如果它发生，那么其所有前驱 $y$（满足 $y \rightarrow x$）中，至少有一个必须发生。

更精确地：设 $\text{pre}[x]$ 是所有直接前驱的集合。如果 $x$ 发生，那么：

$$\bigvee_{y \in \text{pre}[x]} \text{(y发生)}$$

为真（逻辑或）。

3. 确定必然发生的事件

对于已知发生的事件 $x$：

• 如果 $x$ 有唯一前驱 $y$，那么 $y$ 必然发生
• 如果 $x$ 有多个前驱 $y_1, y_2, \dots, y_k$，考虑它们的共同后果：
  • 如果存在事件 $z$，使得所有 $y_i$ 都能推出 $z$，那么 $z$ 必然发生
  • 因为无论哪个 $y_i$ 发生，$z$ 都会发生

---

算法框架

第一步：计算正向传递闭包

使用 bitset 优化，$f[x]$ 是一个 bitset 表示从 $x$ 能推出的所有事件。

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    f[x][x] = 1;  // 自己可以推出自己
    for (auto y : g[x]) {  // g[x]是x的后继
        dfs(y);
        f[x] |= f[y];  // 合并能推出的集合
    }
}

第二步：反向逻辑推导

对于每个事件 $x$，考虑其所有前驱 $\text{rev}[x]$：

• 计算所有前驱能推出的事件的交集
• 这个交集表示：无论哪个前驱发生，这些事件都会发生
• 将这些事件加入 $f[x]$（$x$ 能推出它们）

void solve(int x) {
    if (vis[x]) return;
    vis[x] = true;
    
    int sz = rev[x].size();
    if (sz == 0) return;
    
    bitset<N+5> tmp;
    tmp = ~tmp;  // 初始化为全1
    
    for (auto y : rev[x]) {
        solve(y);
        tmp &= f[y];  // 取所有前驱推出集合的交集
    }
    
    f[x] |= tmp;  // x能推出这些交集事件
}

第三步：传播已知事件

对于每个已知发生的事件 $x$，标记所有 $x$ 能推出的事件为必然发生：

void solve1(int x) {
    if (isv[x]) return;
    isv[x] = 1;
    for (int i = 1; i <= n; i++) {
        if (f[x][i]) {  // x能推出i
            solve1(i);
        }
    }
}

第四步：输出结果

输出所有标记为必然发生的事件。

---

正确性证明

1. 正向传递闭包

$f[x]$ 正确表示从 $x$ 出发能推出的所有事件。由于图是 DAG，递归计算是合理的。

2. 反向推导的交集

关键步骤：对于 $x$ 的所有前驱 $y_i$，计算 $\bigcap_i f[y_i]$。

• 如果某个事件 $z$ 在这个交集中，意味着每个 $y_i$ 都能推出 $z$
• 由于 $x$ 发生，至少有一个 $y_i$ 发生
• 因此 $z$ 必然发生

所以 $x$ 能推出这些 $z$，是正确的。

3. 已知事件的传播

如果 $x$ 已知发生，那么所有 $x$ 能推出的事件必然发生，这是蕴含关系的直接推论。

---

复杂度分析

• 时间复杂度：

  • 计算传递闭包：$O(n^3/64)$，但实际 $O(nm/64)$ 因为使用 bitset
  • 反向推导：类似复杂度
  • 传播已知事件：$O(n^2/64)$
  • 总复杂度可接受，$n \le 1000$

• 空间复杂度：$O(n^2/64)$ 存储 bitset 数组

---

样例分析

样例1

• 推理：$1 \rightarrow 2 \rightarrow 3$
• 已知 $2$ 发生 → $1$ 必然发生（唯一前驱） → $3$ 必然发生（$2$ 推出 $3$）

样例2

• 推理：$1 \rightarrow 3, 2 \rightarrow 3$
• 已知 $3$ 发生，但前驱 $1$ 和 $2$ 的交集为空，无法推出更多

样例3

• 推理：$1 \rightarrow 2, 1 \rightarrow 3, 2 \rightarrow 4, 3 \rightarrow 4$
• 已知 $4$ 发生 → 前驱 $2$ 和 $3$ 的交集为 $\{1,4\}$ → $1$ 必然发生 → $2,3$ 必然发生

---

总结

本题是一道逻辑推理与图论算法的综合题目，主要考察：

1. 传递闭包计算：使用 bitset 优化 DAG 的传递闭包
2. 反向逻辑推导：通过前驱集合的交集找出必然事件
3. bitset 技巧：高效处理集合运算
4. 逻辑推理能力：理解蕴含关系的传递性和逻辑或条件

算法的核心创新在于：

• 使用正向传递闭包记录所有可能的推理链
• 通过反向推导的交集找出"无论哪种情况都发生"的事件
• 利用 bitset 高效实现集合运算

这种"正向闭包+反向交集"的方法是解决逻辑推理网络问题的有效范式，展示了如何将逻辑问题转化为可计算的图论问题。