P1057 [NOIP 2008 普及组] 传球游戏 — 完整分析与证明

1. 题目重述

$n$ 个同学围成一圈，编号 $1, 2, \dots, n$。
球从 1 号开始，每次传球可以传给左边或右边的相邻同学。
传 $m$ 次后，球回到 1 号。
问：有多少种不同的传球方法？

数据范围：$3 \le n \le 30$，$1 \le m \le 30$

2. 问题建模

2.1 环上的位置

$n$ 个人围成圈，位置用模 $n$ 表示：
- 1 号的位置 = 0
- 2 号的位置 = 1
- $i$ 号的位置 = $(i-1) \bmod n$
- 传给右边：位置 +1
- 传给左边：位置 -1

2.2 核心问题

传 $m$ 次后，从位置 0 回到位置 0。
设 $k$ 次向右传，$(m-k)$ 次向左传。

净位移 = $k \cdot (+1) + (m-k) \cdot (-1) = k - (m-k) = 2k - m$

回到起点 $\iff$ 净位移是 $n$ 的整数倍：

\[2k - m \equiv 0 \pmod{n}\]

3. 组合数学解法

3.1 定理

传球方法数 = 满足 $2k \equiv m \pmod{n}$ 的所有 $k$ 对应的组合数之和：

\[\boxed{\text{Answer} = \sum_{\substack{0 \le k \le m \\ 2k \equiv m \pmod{n}}} C_m^k}\]

其中 $C_m^k = \binom{m}{k} = \frac{m!}{k!(m-k)!}$

3.2 证明

Step 1：传球序列与向右次数的一一对应

一个传球序列由 $m$ 次选择组成，每次选"左"或"右"。
如果恰好有 $k$ 次"右"，则序列唯一确定：
从 $m$ 个位置中选 $k$ 个放"右"，其余放"左"。
方法数 = $C_m^k$。

Step 2：回到起点的条件

设 $k$ 次向右，$(m-k)$ 次向左。
净位移 = $k - (m-k) = 2k - m$

在环上，位置是模 $n$ 的，所以：
$$\text{回到起点} \iff 2k - m \equiv 0 \pmod{n}$$

Step 3：求和

所有合法的 $k$ 都对应 $C_m^k$ 种序列，且不同的 $k$ 对应的序列不相交。
由加法原理：
$$\text{Answer} = \sum_{\substack{0 \le k \le m \\ 2k \equiv m \pmod{n}}} C_m^k$$

证毕。

4. 验证样例

4.1 样例：n=3, m=3

条件：$2k \equiv 3 \pmod{3}$

$2k \equiv 0 \pmod{3}$

因为 $\gcd(2,3)=1$，所以 $k \equiv 0 \pmod{3}$

满足条件的 $k$：$0, 3$

\[\text{Answer} = C_3^0 + C_3^3 = 1 + 1 = 2 \quad \checkmark\]

两种方法：
- 全左：1 → 3 → 2 → 1
- 全右：1 → 2 → 3 → 1

4.2 例子：n=4, m=4

条件：$2k \equiv 4 \pmod{4}$

$2k \equiv 0 \pmod{4}$

$k \equiv 0 \pmod{2}$（因为 $2k$ 是 4 的倍数，$k$ 是 2 的倍数）

满足条件的 $k$：$0, 2, 4$

\[\text{Answer} = C_4^0 + C_4^2 + C_4^4 = 1 + 6 + 1 = 8\]

5. 模运算的处理

5.1 负数取模

在 C++ 中，负数 % n 可能为负数：
- $(-3) \% 4 = -3$（不是 1）

正确判断：

if ((2*k - m) % n == 0)  // 可能出错！

// 正确写法：
if ((2*k - m) % n == 0 && (2*k - m) >= 0) 
// 或者统一处理：
int diff = 2*k - m;
if (diff % n == 0)  // 当 diff 非负时 OK
// 更安全的：
if ((diff % n + n) % n == 0)  // 统一为非负

5.2 求解所有合法的 k

$2k \equiv m \pmod{n}$ 是一个线性同余方程。

设 $d = \gcd(2, n)$：
- 如果 $d \nmid m$：无解（但本题中 $m$ 和 $n$ 范围小，直接枚举即可）
- 如果 $d \mid m$：有 $d$ 个模 $n/d$ 的解

由于 $n \le 30, m \le 30$，直接枚举 $k=0$ 到 $m$ 即可，无需解同余方程。

6. 代码实现

6.1 组合公式法（$O(m^2)$ 预处理组合数）

#include <bits/stdc++.h>
using namespace std;

long long C[35][35];  // 组合数表

int main() {
    int n, m;
    cin >> n >> m;

    // 预处理组合数（杨辉三角）
    for (int i = 0; i <= m; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }

    long long ans = 0;
    for (int k = 0; k <= m; k++) {
        int diff = 2 * k - m;
        // 统一处理负数模
        if ((diff % n + n) % n == 0)
            ans += C[m][k];
    }

    cout << ans << endl;
    return 0;
}

6.2 DP 法（$O(nm)$）

更直观，不依赖组合数：

#include <bits/stdc++.h>
using namespace std;

long long dp[35][35];  // dp[i][j] = 传i次后到j号的方法数

int main() {
    int n, m;
    cin >> n >> m;

    dp[0][1] = 1;  // 传0次，在1号（用1-indexed）

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 从左邻居来或从右邻居来
            int left = (j == 1) ? n : j - 1;
            int right = (j == n) ? 1 : j + 1;
            dp[i][j] = dp[i-1][left] + dp[i-1][right];
        }
    }

    cout << dp[m][1] << endl;
    return 0;
}

7. 两种方法对比

方法	时间	空间	优点	缺点
组合公式	$O(m^2)$	$O(m^2)$	数学美感，常数小	需要理解模运算
DP	$O(nm)$	$O(nm)$	直观易懂，好调试	状态转移要细心

对于 $n, m \le 30$，两种方法都 trivial。

推荐：DP 法更稳妥，不易出错。

8. 关键记忆点

传球 = 左右选择 = 每步 +1 或 -1
回到起点 = 净位移 $\equiv 0 \pmod{n}$
$k$ 次向右 = 净位移 $2k - m$
合法序列数 = $C_m^k$（选 $k$ 个位置向右）
总答案 = 所有合法 $k$ 的 $C_m^k$ 之和

9. 拓展思考

9.1 如果传给任意邻居（不只左右）？

如果每人可以传给其他 $n-1$ 人中的任意一个，传 $m$ 次回到 1 号：

这是随机游走问题，用矩阵快速幂或特征值方法解。

9.2 如果要求经过所有人才回到起点？

这是哈密顿回路问题，NP-完全，不可行。

分析完成。