Thuật toán

Gọi ~dp[b][w]~ là số cách xếp ~b~ viên bi đen và ~w~ trắng sao cho các tiền tố có số bi không chênh lệch quá ~D~. Ta có công thức quy hoạch động như sau:

~ dp[0][0] = 1 ~

~ dp[b][w] = \begin{cases} dp[b-1][w] + dp[b][w-1] && \text{nếu }|b-w| \leq D \\ 0 && \text{ngược lại} \end{cases} ~

Code tham khảo

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i) 
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool maximize(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/***End of Template***/
int n, m, d;
const int N = 2005;
int dp[2*N][2*N];
const int MOD = 1e9+7;

void Input() {
    cin >> n >> m >> d;
}

void add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void Solve() {
    memset(dp, 0, sizeof dp);
    dp[0][N] = 1;
    FOR(i, 0, n) FORD(diff, 2*N-1, 0) if (dp[i][diff]) {
        int j = i-(diff-N); 
        if (i < n && abs(diff-N+1) <= d) add(dp[i+1][diff+1], dp[i][diff]);
        if (j < m && abs(diff-N-1) <= d) add(dp[i][diff-1], dp[i][diff]);   
    }
    cout << dp[n][n-m+N];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    Input(), Solve();
    return 0;
}