题意简述

​ 有 $n$ 个人围坐成环，从 $1$ 开始传递，每次可将球传给相邻的人，问 $m$ 次传递后回到 $1$ 的方案数。

思路

分析

​ 这一题很容易想到用搜索算法，但是会超时。我们不妨这样想，如果存在 $m$ 次传递后回到 $1$ 的情况，也就是意味着 $m-1$ 次传递到了 $n$ 或者 $2$ ， $m-2$ 次传递到了 $n-1$ 或者 $3$ 或者 $1$ 。我们就可以脑洞大开一下，求解传递 $k$ 次到 $p$ 的方案数，不就是传递 $k-1$ 次到 $p-1$ 和 $p+1$ 的方案数之和吗？（当然， $p=1$ 时是 $n$ 和 $2$ ）这就是状态的转移。

​ 在这里，我用 f[i][j] 表示经过 $j$ 次传递到 $i$ 的方案数。

​ 有状态转移公式

$$\begin{aligned} f_{i,j}&=f_{i-1,j-1}+f_{i+1,j-1} (i\neq1,i\neq n) \\ f_{i,j}&=f_{n,j-1}+f_{i+1,j-1} (i=1) \\ f_{i,j}&=f_{i-1,j-1}+f_{1,j-1} (i=n) \end{aligned}$$

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, f[35][35];
// f[i][j]=f[i-1][j-1]+f[i+1][j-1]
// f[i][j]表示传到了i 传递了j次的方案数
int main() {
    scanf("%d%d", &n, &m);
    f[1][0] = 1;
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (i == 1)
                f[i][j] = f[n][j - 1] + f[i + 1][j - 1];  // 1可以从n传，也可以从n+1传
            else if (i == n)
                f[i][j] = f[1][j - 1] + f[i - 1][j - 1];  // n可以从1传，也可以从n-1传
            else
                f[i][j] = f[i - 1][j - 1] + f[i + 1][j - 1];  //其余都是i+1,i-1
        }
    }
    cout << f[1][m];
    return 0;
}