题解：图论状态转移与容斥原理的矩阵快速幂优化

---

问题分析

本题要求计算在 $T$ 分钟内从起点1出发，收集齐B、J、M、P四种材料的方案数。关键约束：

• 有 $N$ 个节点，$M$ 条有向边
• 每条边关联一个材料集合（至少包含一种材料）
• 经过边时可以选择是否进入商店：
  • 不进入：耗时1分钟
  • 进入：耗时2分钟（即使不购买）
• 需要收集齐四种材料

方案包括：经过节点的顺序，以及在每条边上是否进入商店（但不关心具体在哪个商店买了什么）。

---

核心观察

1. 状态表示

由于 $T$ 可达 $10^9$，需要高效的状态表示和转移。考虑将状态表示为：

• 当前节点位置
• 已经收集到的材料集合

但材料集合有 $2^4=16$ 种可能，直接状态数为 $N \times 16 = 400$（$N \le 25$），矩阵大小为 $400 \times 400$，可以接受。

2. 时间维度优化

由于每一步转移耗时可能是1或2分钟，直接按分钟转移不可行（$T$ 太大）。

关键技巧：构建状态转移矩阵，使用矩阵快速幂计算 $T$ 分钟后的方案数。

3. 容斥原理

需要收集齐所有四种材料，这可以用容斥原理计算：

$$\text{答案} = \sum_{S \subseteq \{B,J,M,P\}} (-1)^{|S|} \times (\text{只收集 } S \text{ 中材料的方案数}) $$

其中 $S$ 是要求至少不包含的材料集合（即可以缺少这些材料）。

---

算法框架

第一步：构建状态图

将每个节点 $i$ 拆分为两个状态：

• $i$：刚到达节点 $i$，还未决定是否进入商店
• $i+N$：在节点 $i$ 处选择了进入商店（耗时增加）

额外添加一个终止状态 $(2N+1)$，用于统计所有有效路径。

第二步：转移矩阵构建

对于每个材料集合限制 $T$（容斥中的"允许缺少的材料集合"），构建转移矩阵 $G_T$：

1. 基础转移：

   • $i \to i+N$：选择进入商店
   • $i \to j$：从 $i$ 到 $j$ 不进入商店，耗时1
   • $i+N \to j$：从 $i$ 到 $j$ 进入商店，耗时2

2. 材料约束转移：

   • 对于边 $(u,v)$ 提供材料集合 $S_i$
   • 如果 $S_i$ 是 $T$ 的子集（即 $S_i \& T = S_i$），则允许从 $u+N$ 转移到 $v$
   • 这表示：如果边上的材料都在"允许缺少"的集合中，那么进入商店后可以直接转移到下一节点

3. 终止状态：

   • 从起点1可以到达终止状态
   • 终止状态自环，吸收所有路径

第三步：矩阵快速幂

计算 $G_T^{T+1}$，其中 $T+1$ 是因为：

• 矩阵的 $k$ 次幂表示走 $k$ 步后的方案数
• 我们需要恰好 $T$ 分钟，但矩阵包含"额外"的终止状态转移

第四步：容斥计算

对所有 $T \subseteq \{B,J,M,P\}$（共16种）：

• 计算 $G_T^{T+1}$
• 获取从起点1到终止状态的方案数
• 根据 $|T|$ 的奇偶性加或减

---

关键实现细节

材料编码

// B=8(1000), J=4(0100), M=2(0010), P=1(0001)
if (c == 'B') S[i] |= 8;
else if (c == 'J') S[i] |= 4;
else if (c == 'M') S[i] |= 2;
else if (c == 'P') S[i] |= 1;

矩阵快速幂

Matrix operator ^= (const int &x) {
    Matrix bas = *this, ret;
    ret.INIT(n);  // 单位矩阵
    int k = x;
    while (k) {
        if (k & 1) ret *= bas;
        bas *= bas;
        k >>= 1;
    }
    *this = ret;
}

容斥计算

FOR(T_mask, 0, 15) {
    // 构建G_T
    G ^= t + 1;
    if (__builtin_popcount(T_mask) & 1)
        ans = (ans - G.GetAns(1, n<<1|1) + Mod) % Mod;
    else
        ans = (ans + G.GetAns(1, n<<1|1)) % Mod;
}

---

复杂度分析

• 矩阵大小：$2N+1 \le 51$
• 矩阵乘法：$O((2N+1)^3) \approx 51^3 \approx 1.3\times 10^5$
• 快速幂：$O(\log T) \approx 30$ 次矩阵乘法
• 容斥：16种材料集合
• 总复杂度：$O(16 \times 30 \times 51^3) \approx 6\times 10^7$，可接受

---

正确性证明

1. 状态拆分的正确性

将节点拆分为"未进商店"和"已进商店"状态，准确建模了1分钟和2分钟两种耗时情况。

2. 容斥原理的正确性

设 $A_i$ 为缺少材料 $i$ 的方案集合，则：

$$\text{全收集方案} = \text{总方案} - \bigcup_{i} A_i$$

由容斥原理：

$$\left| \bigcap_i \overline{A_i} \right| = \sum_{S \subseteq \{B,J,M,P\}} (-1)^{|S|} \left| \bigcap_{i \in S} A_i \right| $$

其中 $\bigcap_{i \in S} A_i$ 表示至少缺少 $S$ 中所有材料的方案数。

3. 终止状态的正确性

终止状态确保我们统计的是恰好 $T$ 分钟内完成采购的方案，因为：

• 从起点到终止状态代表完成一次采购
• 终止状态自环允许任意额外时间"停留"

---

总结

本题是一道图论、矩阵快速幂与容斥原理综合的高级题目，主要考察：

1. 状态设计能力：将时间、位置、材料集合巧妙编码到矩阵中
2. 矩阵快速幂应用：处理超大时间范围的路径计数
3. 容斥原理：处理"必须包含所有元素"的条件
4. 位运算技巧：高效处理材料集合的包含关系

算法的核心技巧：

• 使用节点拆分建模1/2分钟耗时差异
• 通过矩阵快速幂在 $O(\log T)$ 时间内计算方案数
• 利用容斥原理将"必须全收集"转化为多个"允许缺少"的子问题

这种"状态矩阵+快速幂+容斥"的方法是解决带约束的路径计数问题的强大工具，尤其适用于时间范围极大的情况。