[NOIP 2008 普及组] 传球游戏

题意

n 个同学围成一个圆圈，开始时球在 1 号同学手里。

每次传球时，当前拿球的人只能把球传给左边或右边的同学。

问恰好传 m 次以后，球又回到 1 号同学手里的方案数。

思路

最直接的办法是把每一步都看成一个二选一：

往左传
往右传

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include <bits/stdc++.h>
using namespace std;

// brute.cpp：暴力搜索每一步往左传还是往右传。

int n, m;
long long ans;

int left_pos(int x) {
    if (x == 1) {
        return n;
    }
    return x - 1;
}

int right_pos(int x) {
    if (x == n) {
        return 1;
    }
    return x + 1;
}

void dfs(int step, int pos) {
    if (step == m) {
        if (pos == 1) {
            ans++;
        }
        return;
    }

    dfs(step + 1, left_pos(pos));
    dfs(step + 1, right_pos(pos));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    ans = 0;
    dfs(0, 1);

    cout << ans << '\n';
    return 0;
}

brute.cpp 用 DFS 枚举每一步向左还是向右，做满 m 步后判断球是否回到 1 号。

这个方法能直观看出题意，但会把很多“传了同样次数、球在同样位置”的情况重复计算。

更合适的方法是做动态规划。

设：

dp[i][j] = 传了 i 次后，球在 j 号同学手里的方案数

如果第 i 次后球在 j，那么第 i-1 次后球只能在 j 的左邻居或右邻居。

所以转移式就是：

dp[i][j] = dp[i-1][left(j)] + dp[i-1][right(j)]

其中 left(j) 和 right(j) 要按圆圈处理：

1 的左边是 n
n 的右边是 1

初始状态：

dp[0][1] = 1

表示开始前球在 1 号同学手里的唯一一种情况。

状态表

以样例 $n = 3, m = 3$ 为例：

传球次数 `i`	`1` 号	`2` 号	`3` 号
0	`1`	`0`	`0`
1	`0`	`1`	`1`
2	`2`	`1`	`1`
3	`2`	`3`	`3`

所以 dp[3][1] = 2，答案就是 2。

DP 公式

设 $dp_{i,j}$ 表示传了 $i$ 次后，球在 $j$ 号同学手里的方案数。初始化：

dp_{0,1}=1

记环上的左右邻居为 $left(j)$ 和 $right(j)$ ，则：

dp_{i,j}=dp_{i-1,left(j)}+dp_{i-1,right(j)}

最终答案为：

dp_{m,1}

公式解释：传完第 i 次后球在 j 手里，上一轮一定在 j 的左邻居或右邻居手里。两个来源的方案互不重叠，直接相加就是当前位置的新方案数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, m;
long long dp[MAXN][MAXN];

int left_pos(int x) {
    if (x == 1) {
        return n;
    }
    return x - 1;
}

int right_pos(int x) {
    if (x == n) {
        return 1;
    }
    return x + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    // 传球开始前，球在 1 号同学手里。
    dp[0][1] = 1;

    for (int step = 1; step <= m; step++) {
        for (int pos = 1; pos <= n; pos++) {
            // 这一步结束后球在 pos，说明上一步球在它左右两边之一。
            dp[step][pos] = dp[step - 1][left_pos(pos)] + dp[step - 1][right_pos(pos)];
        }
    }

    cout << dp[m][1] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(nm)$

总结

这题本质上是在环上走 m 步并统计回到起点的方案数。

核心就是把状态定义成“传了多少次、球在谁手里”，然后由左右相邻位置转移过来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。