传球游戏

题目描述

$n$ 个同学围成一圈，编号 $0 \sim n-1$ （小蛮为 $0$ 号）。球最初在 $0$ 号手中，每次必须传给左右相邻同学之一。求恰好传 $m$ 次后球回到 $0$ 号手中的方案数。

输入格式：一行两个整数 $n, m$ （ $3 \le n \le 30, 1 \le m \le 30$ ）。

输出格式：一个整数，表示方案数。

样例输入：3 3，样例输出：2。

思路

设 $f(i, j)$ 为传 $i$ 次后球在 $j$ 号手中的方案数，则 $f(i, j) = f(i-1, (j-1) \bmod n) + f(i-1, (j+1) \bmod n)$ ，边界 $f(0, 0) = 1$ ，答案 $f(m, 0)$ 。直接按次数逐层递推即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17import sys
from functools import cache


def solve(n: int, m: int) -> int:
    """f(i, j)：传 i 次后球在 j 号手里的方案数，邻居环上取模。"""
    @cache
    def f(i: int, j: int) -> int:
        if i == 0:
            return j == 0  # 开始时球在 1 号（下标 0）手里
        return f(i - 1, (j - 1) % n) + f(i - 1, (j + 1) % n)  # 一次只能从左右邻居传来
    return f(m, 0)


data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
print(solve(n, m))

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:05
 * update_at: 2026-10-06 14:05
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m;
// dp[i][j] 表示传 i 次后球在 j 号同学手中的方案数
ll dp[35][35];

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

    cin >> n >> m;

    dp[0][0] = 1; // 初始球在小蛮（0 号）手中

    for (ll i = 1; i <= m; i++) {
        for (ll j = 0; j < n; j++) {
            ll left = (j - 1 + n) % n;  // j 的左邻居
            ll right = (j + 1) % n;     // j 的右邻居
            dp[i][j] = dp[i - 1][left] + dp[i - 1][right];
        }
    }

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

目录

题目描述

思路

参考代码