[NOIP 2008 普及组] 传球游戏

知识点

动态规划、环形状态

解题思路

dp[i]表示当前传球次数后球在i号同学的方案数，初态dp[0]=1。每一步把dp[i]分别累加到左右相邻位置。m步后输出dp[0]。

正确性说明

任何长k+1的传递方案由唯一的长k前缀和最后一次向左/右传球组成。n≥3使左右邻居不同，两个转移互斥；逐步累加恰好计入所有方案且不重计。

易错点

下标按n取模；每一步用新数组，不能在同一层原地传播；计数使用64位。

复杂度

时间O(nm)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<long long>d(n),v(n);d[0]=1;for(int t=0;t<m;t++){fill(v.begin(),v.end(),0);for(int i=0;i<n;i++)v[(i+1)%n]+=d[i],v[(i+n-1)%n]+=d[i];d.swap(v);}cout<<d[0]<<'\n';}