[DP记录]AT2370 [AGC013D] Piling Up

**题意** ： 一开始袋子中有 $n$ 个黑白球，但不知道黑白色各有多少。 进行 $m$ 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球。 将拿出的球按顺序排列，求形成的颜色序列有多少种。答案对 $10^9+7$ 取模。 $n,m\leq 3000$ ，时限$\texttt{2s}$。 ------------ 不难发现，操作后袋子中的总球数不变。 先考虑给定初始时有 $x$ 个黑球的情况。 $dp[i][j]$ 表示进行了 $i$ 次操作，目前袋子中有 $j$ 个黑球的方案数。 边界为 $dp[0][x]=1$。 操作时，分三种情况讨论 ： - 取出黑黑 ： 黑球个数减少一个， $dp[i+1][j-1]{\texttt{ += }}dp[i][j]$ - 取出白白 ： 黑球个数增加一个， $dp[i+1][j+1]{\texttt{ += }}dp[i][j]$ - 取出黑白或白黑 ： 黑球个数不变， $dp[i+1][j]{\texttt{ += }}2dp[i][j]$ 特殊地，当 $j=0$ 时，不能取黑白，当 $j=n$ 时，不能取白黑。 现在考虑初始时黑球数目不定的情况。似乎只需要将 $dp[0][0\sim n]$ 都置为 $1$ 就好了？ 这样会导致重复计数。我们将一个操作方案中袋中黑球的变化情况画成折线，平移后能重合的折线产生的颜色序列是相同的，但却被统计了多次。 于是，我们只统计接触过 $x$ 轴的折线（即中途黑球个数曾为 $0$ 的方案），这样就不会重复了。 多开一维 $0/1$ 记录这个。 复杂度 $O(n^2)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 3050 using namespace std; const int mod=1000000007; int n,m,dp[MaxN][MaxN][2]; int main() { scanf("%d%d",&n,&m); dp[0][0][1]=1; for (int j=1;j<=n;j++) dp[0][j][0]=1; for (int i=0;i<m;i++) for (int j=0;j<=n;j++){ if (j>0){ if (j==1)dp[i+1][j-1][1]=(dp[i+1][j-1][1]+dp[i][j][0])%mod; else dp[i+1][j-1][0]=(dp[i+1][j-1][0]+dp[i][j][0])%mod; dp[i+1][j-1][1]=(dp[i+1][j-1][1]+dp[i][j][1])%mod; if (j==1)dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][0])%mod; else dp[i+1][j][0]=(dp[i+1][j][0]+dp[i][j][0])%mod; dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][1])%mod; } if (j<n){ dp[i+1][j+1][0]=(dp[i+1][j+1][0]+dp[i][j][0])%mod; dp[i+1][j+1][1]=(dp[i+1][j+1][1]+dp[i][j][1])%mod; dp[i+1][j][0]=(dp[i+1][j][0]+dp[i][j][0])%mod; dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][1])%mod; } } int ans=0; for (int j=0;j<=n;j++) ans=(ans+dp[m][j][1])%mod; printf("%d",ans); return 0; } ```