题目分析

本题要求计算在特定网络拓扑下，使得每条有向边恰好使用一次的路由方案数量。网络具有以下重要特性：

网络结构特征

• 网络由 $N$ 个节点组成（$2 \leq N \leq 100$）
• 除最多 $K$ 条反向边外（$0 \leq K \leq 2$），所有边满足 $i < j$
• 网络中不存在自环
• 发送者数量 $S$ 等于接收者数量，且 $S \geq 1$

问题转化

我们需要找到 $S$ 条从不同发送者到不同接收者的路径，使得：

• 所有路径的边集合构成整个网络边集的划分
• 每条边在且仅在一个路径中出现
• 节点可以在同一条路径中重复出现

算法思路

情况一：$K = 0$（无反向边）

当网络为纯DAG时，解决方案较为简单：

• 每个节点的方案数由其出度决定
• 总方案数为所有节点出度阶乘的乘积

情况二：$K = 1$（一条反向边）

使用容斥原理处理：

1. 计算不考虑反向边时的基础方案数
2. 减去包含反向边环路的非法方案
3. 通过动态规划计算反向边的影响

情况三：$K = 2$（两条反向边）

处理更为复杂，需要综合考虑：

1. 分别处理每条反向边的影响
2. 计算两条反向边同时出现的交互影响
3. 使用二维动态规划跟踪两条路径的状态

关键技巧

容斥原理应用

通过基础方案减去非法方案，再加回重复减去的部分，确保计数准确。

动态规划优化

• 对于 $K = 1$：使用一维DP跟踪单条路径
• 对于 $K = 2$：使用二维DP同时跟踪两条路径

模运算处理

由于答案可能很大，需要在计算过程中对 $10^9 + 7$ 取模。

复杂度分析

• 时间复杂度：$O(T \cdot N^2)$，满足题目约束
• 空间复杂度：$O(N^2)$，用于存储图结构和DP状态

实现要点

1. 预处理：计算阶乘和模逆元，优化组合数计算
2. 图构建：根据输入构建邻接表表示
3. 度数计算：考虑节点类型（发送者/接收者）对度数的影响
4. 路径统计：按照 $K$ 的不同取值采用相应算法

算法标签

• 欧拉回路

• 矩阵树定理

• 组合数学

• 动态规划

• 容斥原理

• 网络流

总结

本题通过分析网络拓扑的特殊性质，针对不同 $K$ 值设计相应算法，结合容斥原理和动态规划技术，高效解决了复杂网络中的路由方案计数问题。算法充分利用了题目约束条件，实现了在合理复杂度内的精确计算。