Piling Up
一个很好的思路就是设 \(f[i][j]\) 表示当前进行了 \(i\) 步，并且盒子中剩下了 \(j\) 个白球的方案数，然后直接 DP 即可。
但是这样是有问题的，它没有考虑到重复计算的问题。
我们不妨令 \(+\) 符号表示取出黑球，\(-\)符号表示取出白球。
则一种方式是 \(6\xrightarrow{+-}6\xrightarrow{--}5\)，其中数字表示剩余白球数。
另一种方式是 \(4\xrightarrow{+-}4\xrightarrow{--}3\)。很明显，两者即使盒中球数不同，但是序列是相同的。
为了避免重复计算，我们可以强制要求只有过程中出现过 0 的序列才是合法序列。
于是我们可以设 \(f[i][j][0/1]\) 表示进行 \(i\) 步，盒子中剩下 \(j\) 个白球，且（没有/有）到过 0 的方案数。则答案即为 \(\sum\limits_{i=0}^nf[m][i][1]\)。
要注意的是，这里的转移过程必须保证任意时刻球的数量必须在 \([0,n]\) 范围之内，因此对于不合法的状态要记得特判掉。
复杂度 \(O(nm)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=3e3+100;
int n,m,ans;
int f[N][N][2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<=n;i++) f[0][i][i==0]=1;
for(int i=0;i<m;i++){
for(int j=0;j<=n;j++){
if(j){
(f[i+1][j][j==1]+=f[i][j][0])%=mod;
(f[i+1][j][1]+=f[i][j][1])%=mod;//-+
(f[i+1][j-1][j==1]+=f[i][j][0])%=mod;
(f[i+1][j-1][1]+=f[i][j][1])%=mod;//--;
}
if(j<n){
(f[i+1][j][0]+=f[i][j][0])%=mod;
(f[i+1][j][1]+=f[i][j][1])%=mod;//+-
(f[i+1][j+1][0]+=f[i][j][0])%=mod;
(f[i+1][j+1][1]+=f[i][j][1])%=mod;//++;
}
}
}
for(int i=0;i<=n;i++) (ans+=f[m][i][1])%=mod;
cout<<(ans+mod)%mod;
return 0;
}