算法

(DP,环形DP) $O(NM)$

不妨设小蛮在0号，所有人的编号是 $0 \sim n-1$。

状态表示 f[i, j]：

• 集合：所有已经传了i次球，且最后球在编号是j的小朋友手上的方案；
• 属性：集合中元素的数量；

状态计算：

• f[i, j]所表示的集合可以划分成两个子集：
  • 从左边传过来的集合大小是f[i, j - 1]；
  • 从右边传过来的集合大小是f[i, j + 1]；
• f[i, j]等于两个子集的元素数之和。

注意当j = 0或j = n - 1时需要特殊处理边界。

最终答案就是f[[m][0]。

时间复杂度

总共有 $NM$ 个状态，计算每个状态需要 $O(1)$ 的时间，因此总时间复杂度是 $O(NM)$。

C++ 代码

#include <iostream>

using namespace std;

const int N = 35;

int n, m;
int f[N][N];

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

    f[0][0] = 1;
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j < n; j ++ )
            f[i][j] = f[i - 1][(j + n - 1) % n] + f[i - 1][(j + 1) % n];

    cout << f[m][0] << endl;

    return 0;
}