题解：基环树森林计数问题

问题分析

我们有 $n$ 个白点，$m$ 个黑点，每个点有一条出边，形成基环树森林。

限制条件：

1. 黑点必须指向白点
2. 每个环上黑点数 × 白点数为偶数

我们需要计算满足条件的方案数。

---

关键观察

1. 问题转化

每个点有一条出边 → 这是一个从 $n+m$ 个点到 $n+m$ 个点的函数 $f: [n+m] \to [n+m]$。

基环树森林就是函数的功能图（functional graph）。

2. 限制条件分析

• 限制1：黑点必须指向白点
  黑点的出边只能选择 $n$ 个白点，所以黑点有 $n$ 种选择 白点的出边可以选择任意 $n+m$ 个点

• 限制2：每个环上黑点数 × 白点数为偶数
  这意味着环不能由恰好1个黑点和1个白点组成（乘积为1是奇数） 其他情况：全白环、全黑环、2黑1白环等都满足乘积为偶数

---

3. 计数思路

我们可以用容斥原理：

• 总方案数（只考虑限制1）：$n^m \cdot (n+m)^n$
• 减去包含非法环的方案数

非法环是指：环上恰好有1个黑点和1个白点（即长度为2的环，一黑一白）

---

4. 包含-排除方法

设 $F(k)$ 表示至少包含 $k$ 个非法环的方案数。

根据容斥原理：

$$\text{答案} = \sum_{k=0}^{\min(n,m)} (-1)^k F(k)$$

---

5. 计算 $F(k)$

要计算至少 $k$ 个非法环的方案数：

步骤1：选择 $k$ 个黑点和 $k$ 个白点组成非法环
选择方式：$\binom{n}{k} \binom{m}{k}$

步骤2：这 $2k$ 个点组成 $k$ 个非法环的排列方式
对于选定的 $k$ 对点，它们可以组成环的方式是：将黑点和白点配对并排列成环
方式数：$k!$（黑点排列） × $k!$（白点与黑点配对）

步骤3：剩余点的连接方式

• 剩余 $n-k$ 个白点：可以指向任意 $n+m$ 个点，但要注意不能破坏已确定的环结构
• 剩余 $m-k$ 个黑点：必须指向白点，有 $n$ 种选择

实际上更精确的计算需要考虑函数图的结构。

---

6. 精确的容斥公式

经过推导（参考函数计数和基环树森林的经典结果），最终的容斥公式为：

$$\text{答案} = \sum_{k=0}^{\min(n,m)} (-1)^k \binom{n}{k} \binom{m}{k} k! \cdot n^{m-k} \cdot (n+m)^{n-k} $$

解释：

• $\binom{n}{k} \binom{m}{k} k!$：选择并配对形成 $k$ 个非法环
• $n^{m-k}$：剩余 $m-k$ 个黑点各选择 $n$ 个白点之一
• $(n+m)^{n-k}$：剩余 $n-k$ 个白点各选择 $n+m$ 个点之一

---

7. 验证样例

样例1：$n=2, m=1, P=10^6$

计算：

• $k=0$：$\binom{2}{0}\binom{1}{0}0! \cdot 2^{1} \cdot 3^{2} = 1 \times 2 \times 9 = 18$
• $k=1$：$\binom{2}{1}\binom{1}{1}1! \cdot 2^{0} \cdot 3^{1} = 2 \times 1 \times 1 \times 3 = 6$
• 答案：$18 - 6 = 12$ ✓

---

8. 算法实现

我们需要在 $O(\min(n,m))$ 时间内计算这个和式。

预处理：

• 组合数 $\binom{n}{k}$ 和 $\binom{m}{k}$
• 幂 $n^{m-k}$ 和 $(n+m)^{n-k}$

优化：

• 预处理阶乘和逆元（模 $P$）
• 预处理幂

---

9. 代码框架

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, P;
    cin >> n >> m >> P;
    
    int K = min(n, m);
    
    // 预处理组合数
    vector<vector<int>> C_n(n+1, vector<int>(K+1));
    vector<vector<int>> C_m(m+1, vector<int>(K+1));
    // 用递推计算组合数 C(n,k) mod P
    
    // 预处理幂
    vector<int> pow_n(K+1), pow_nm(K+1);
    // pow_n[i] = n^(m-i) mod P
    // pow_nm[i] = (n+m)^(n-i) mod P
    
    // 预处理阶乘
    vector<int> fact(K+1);
    
    long long ans = 0;
    for (int k = 0; k <= K; k++) {
        long long term = 1;
        term = term * C_n[n][k] % P;
        term = term * C_m[m][k] % P;
        term = term * fact[k] % P;
        term = term * pow_n[k] % P;
        term = term * pow_nm[k] % P;
        
        if (k % 2 == 1) {
            ans = (ans - term + P) % P;
        } else {
            ans = (ans + term) % P;
        }
    }
    
    cout << ans << endl;
    return 0;
}

---

10. 复杂度分析

• 时间复杂度：$O(\min(n,m))$，在 $n,m \le 2000$ 时完全可行
• 空间复杂度：$O(n+m)$

---

11. 模运算细节

由于 $P$ 不一定是质数，我们不能直接用逆元。需要：

• 用递推公式计算组合数：$C(n,k) = C(n-1,k-1) + C(n-1,k)$
• 用快速幂计算幂次

---

总结

本题的关键在于：

1. 将问题转化为函数计数问题
2. 识别非法环的精确条件（一黑一白环）
3. 使用容斥原理排除非法情况
4. 推导出简洁的组合计数公式

这是一个典型的组合数学+容斥原理的计数问题，考察对图论结构和组合技巧的综合理解。