前言
NOIP 模拟联考题，赛时随手打了一个暴力，赛后随便想想整出个做法，发现这里没有，那就发一下吧。
思路
设当前黑白球分别有 \(a,b\) 个。
注意到这个变化过程可以在二维平面上很轻松地表现出来。
每一步形如加一个向量，则发现其实运动轨迹可以视为在一条直线上。
问题在于：如何统计答案？
我们发现，任何一个运动轨迹，只要其运动的左端点与右端点距离不超过 \(n\)，则其必然可行。
于是先设计一个 \(O(n^2m)\) 的暴力 dp：
设走了 \(m\) 步，当前运动所到达的最左端点与当前点距离为 \(a\)，所到达的最右端点与当前点距离为 \(b\)，此时的方案数为 \(f_{m,a,b}\)。
容易写出此 dp：
A[0][0]=1;
for(uint i=0;i<m;i++){
for(uint j=0;j<=n;j++)for(uint k=0;j+k<=n;k++)Last[j][k]=A[j][k],A[j][k]=0;
for(uint j=0;j<=n;j++)for(uint k=0;j+k<=n;k++)
{
A[std::max(j,1u)][k]+=Last[j][k];
A[j][std::max(k,1u)]+=Last[j][k];
A[j?j-1:0][k+1]+=Last[j][k];
A[j+1][k?k-1:0]+=Last[j][k];
}
}
然后答案即为 \(\sum_a\sum_b[a+b\le n]f_{m,a,b}\)。
但是这个 dp 很不优美。
我们怀疑这和 \(f\) 的设计有关。
我们考虑设 \(g_{m,n,a}\) 表示走了 \(m\) 步，当前运动所到达的最左端点与当前点距离不大于 \(a\)，所到达的最右端点与所到达的左端点距离不大于 \(n\)，此时的方案数。
为了方便接下来推导，我们暂时忽视 \(m\) 这一维。
则对两个端点简单容斥得到 \(f_{a,b}=g_{a+b,a}-g_{a+b-1,a}-g_{a+b-1,a-1}+g_{a+b-2,a-1}\)。
于是
\[\sum_a\sum_b[a+b\le n]f_{a,b} \\=\sum_{i=0}^n\sum_a g_{i,a}-\sum_{i=0}^{n-1}\sum_a g_{i,a}-\sum_{i=0}^{n-1}\sum_a g_{i,a}+\sum_{i=0}^{n-2}\sum_a g_{i,a} \\=(\sum_a g_{n,a})-(\sum_a g_{n-1,a}) \]我们发现，原来我们只用求出两行 \(g\) 即可。
但是 dp 转移方程还是太恶心了。
于是设 \(h_{2m,2n,2a}=g_{m,n,a}\)。
则
\[h_{m,n,a}=[a>0]h_{m-1,n,a-1}+[a<n]h_{m-1,n,a+1} \]容易验证这个 dp 方程满足要求。
你发现 \(n\) 这一维在 dp 过程中是常数，于是忽视即可。
于是就得到一个 \(O(nm)\) 做法，滚动数组即可通过。
然而似乎可以做的更好？
注意到这个转移方程中 \((m,a)\) 之间的贡献关系写到二维平面上形如格路计数的形式。
于是使用反射容斥法即可算出单点点值，总复杂度为 \(O(n\min\{n,m\})\)，由于 \(m\le n\) 时答案显然 \(4^m\)，所以就是 \(O(n^2)\) 啦！
Code
以下是 dp 部分代码。
typedef AnyMod::ModInt modint;
modint A[6005],Last[6005];
int main(){
#ifdef MYEE
freopen("QAQ.in","r",stdin);
#endif
uint n,m;scanf("%u%u",&n,&m);AnyMod::ChgMod(1e9+7);
for(uint i=0;i<=n*2;i+=2)A[i]=1;
for(uint i=1;i<=m*2;i++)for(uint j=i&1;j<=n*2;j+=2)
{
A[j]=0;
if(j)A[j]+=A[j-1];
if(j<(n*2))A[j]+=A[j+1];
}
modint ans;
for(uint i=0;i<=n*2;i+=2)ans+=A[i];
for(uint i=0;i<=n*2-2;i+=2)A[i]=1;
for(uint i=1;i<=m*2;i++)for(uint j=i&1;j<=n*2-2;j+=2)
{
A[j]=0;
if(j)A[j]+=A[j-1];
if(j<(n*2-2))A[j]+=A[j+1];
}
for(uint i=0;i<=n*2-2;i+=2)ans-=A[i];
ans.println();
return 0;
}