20221005_T1C_思维dp

题意

一开始有 \(n\) 个颜色为黑白的球，但不知道黑白色分别有多少， \(m\) 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。答案对 \(10^9+7\) 取模。

\(n,m\) 小于等于 \(3000\)。

题解

赛时得分：0/100

并不简单的一道题。

如果就进行普通的 dp 因为各种重复的问题显然不对，现在主要问题就是如何去重。

假如说白球个数是 \(x\)，那么黑球个数就是 \(n-x\) 个。结论是，我们只需要取白球个数中途恰好为 0 的那些方法。

为什么不会遗漏。因为任意的方法，只要合法，我向下移到 0 的位置总归是成立的。（这里在说那张图）为什么不会重复，因为如果两个东西重复了，那么偏移量不可能是 0，但是向上偏移就不满足有 0 了，向下偏移就不满足球的个数是正数了。

既然已经知道了取过 0 的，如果快速计算呢？

我们只需要用 \(n\) 的答案减去 \(n-1\) 的答案就好了，因为 \(n-1\) 的答案你可以恰好认为固定放了一个白球在盒子里，那么这样的话白球个数不可能为 0，这也就是重复算的情况。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 3e3 + 10, inf = 0x3f3f3f3f;

int n, m;

const int P = 1e9 + 7;

int dp[N][N];

int solve(int n) {
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= n; ++i) dp[1][i] = 1;
    for(int i = 2; i <= m; ++i) {
        for(int j = 0; j <= n; ++j) {
            if(j) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % P;
            if(n - j) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % P;
            if(j) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % P;
            if(n - j) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % P;
        }
    }
    int ans = 0;
    for(int i = 0; i <= n; ++i) ans = (ans + dp[m][i]) % P;
    return ans;
}

int main() {
    // freopen("easyhard.in", "r", stdin);
    // freopen("easyhard.out", "w", stdout);
    read(n, m); ++m;
    cout << (solve(n) - solve(n - 1) + P) % P << endl;
    return 0;
}