分析
这道题可以用 dp 来做。设 \(f_{i,j}\) 为第 \(j\) 次传球传到第 \(i\) 个人的方案数。那么
\[f_{i,j}=\begin{cases}1,&i=1\&j=0,\\f_{n,j-1}+f_{2,j-1}&i=1,\\f_{1,j-1+f_{n-1,j-1}}&i=n,\\f_{i-1,j-1}+f_{i+1,j-1},&otherwise.\end{cases} \]需要注意边界的处理。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[35][35];
int main() {
cin >> n >> m;
f[1][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j == 1)f[j][i] += f[n][i - 1] + f[2][i - 1];
else if (j == n)f[j][i] += f[1][i - 1] + f[n - 1][i - 1];
else f[j][i] += f[j - 1][i - 1] + f[j + 1][i - 1];
}
}
cout << f[1][m];
return 0;
}