Subtask 1

Dùng backtrack hoặc bitmask để sinh hết tất cả các xâu nhị phân ~s~ chứa tối đa ~a_0~ chữ số ~0~ và ~a_1~ chữ số ~1~, và cộng đáp án lên ~1~ nếu xâu ~s~ thỏa mãn mọi điều kiện của đề bài.

Độ phức tạp: ~\mathcal{O}(2^{a_0 + a_1}(a_0 + a_1))~

Subtask 2

Dãy sẽ có dạng gồm các chữ số ~0~ liên tiếp rồi các chữ số ~1~ liên tiếp, các chữ số ~0~ liên tiếp,... tiếp tục lặp lại như thế. Coi các chữ số ~0~ và ~1~ liên tiếp là một số duy nhất (một cụm).

Gọi ~dp[i][j][\text{last}]~ là số xâu thoả mãn đề sao cho có ~i~ số ~0~, ~j~ số ~1~ và ~\text{last}~ là chữ số cuối cùng của xâu. Xét độ dài của cụm cuối cùng là ~l~, nếu ~\text{last} = 0~ thì ta có ~b_0 \leq l \leq i~, ngược lại có ~b_1 \leq l \leq j~. Ta duyệt qua tất cả các độ dài ~l~ có thể và cập nhật vào trạng thái ~dp~ tương ứng. Như thế ta có:

$$ \begin{align} dp[i][j][0] &= \displaystyle\sum_{l = b_0}^{i}{dp[i - l][j][1]} \\ dp[i][j][1] &= \displaystyle\sum_{l = b_1}^{j}{dp[i][j - l][0]} \\ \end{align} $$

Có thể lấy ~dp[0][0][0] = dp[0][0][1] = 1~ làm cơ sở.

Độ phức tạp: ~\mathcal{O}(N^3)~.

Subtask 3

Ở subtask 2, để ý rằng ta cần tính tổng của một đoạn liên tiếp theo ~i~ hoặc ~j~, nên ta có thể dựng mảng cộng dồn để tính nhanh các tổng đó. Cụ thể hơn ta có thể dựng 2 mảng ~pre_i[i][j] = \sum_{k = 0}^{i}{dp[k][j][1]}~ và ~pre_j[i][j] = \sum_{k = 0}^{j}{dp[i][k][0]}~, rồi cùng tính song song 2 mảng này khi đang tính ~dp~.

Độ phức tạp: ~\mathcal{O}(N^2)~.

Subtask 4

Viết lại dãy gồm các cụm như trên ta sẽ có dạng ~x_1y_1x_2y_2\dots~ với ~x_i~ là số chữ số ~0~ trong cụm thứ ~i~ của ~0~, ~y_i~ là số chữ số ~1~ trong cụm thứ ~i~ của ~1~. Từ đó, với dãy ~x~, ta có thể đưa bài toán về tìm số nghiệm của phương trình: ~x_1 + x_2 + \cdots + x_k \leq a_0~ với ~x_i \ge b_0~, và tương tự với dãy ~y~. Thay ~u_i = x_i - b_0~, ta có:

$$ u_1 + u_2 + \cdots + u_k \leq a_0 - k \cdot b_0,\ u_i \ge 0 $$

Đáp án chính là số nghiệm của phương trình ~u_1 + u_2 + \cdots + u_k + u_{k + 1} = a_0 - k \cdot b_0~ thoả ~u_i \ge 0\ \forall i \in [1, k + 1]~, và là:

$$ \binom{a_0 - k \cdot b_0 + (k + 1) - 1}{(k + 1) - 1} = \binom{a_0 - k \cdot b_0 + k}{k} $$

Với mỗi tập nghiệm của ~x~ gồm ~k~ phần tử, ta có thể ghép với tất cả các tập nghiệm của ~y~ có ~k~ hoặc ~k - 1~ phần tử và ngược lại.

Độ phức tạp: ~\mathcal{O}(N\log{N})~.

Code mẫu

/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;

int a0, a1;
int b0, b1;


int ans0[maxn], ans1[maxn];
int fac[maxn], ifac[maxn];
int C(int k, int n){
    return fac[n] * ifac[n - k] % MOD * ifac[k] % MOD;
}

int binpow (int x, int y){
    if (y == 0) return 1;

    int t = binpow(x, y >> 1);
    t = (t * t) % MOD;
    if (y & 1) t = (t * x) % MOD;
    return t;
}
void prep(){
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) fac[i] = (fac[i - 1] * i) % MOD;
    ifac[maxn - 1] = binpow(fac[maxn - 1], MOD - 2);

    for (int i = maxn - 1; i >= 1; i--){
        ifac[i - 1] = (ifac[i] * i) % MOD;
    }

}

void add (int &x, int y){
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void PROGRAM(int _){
    cin >> a0 >> a1 >> b0 >> b1;

    for (int i = 0; i <= max(a0, a1); i++){
        ans0[i] = ans1[i] = 0;
    }

    for (int k = 1; k <= a0 / b0; k++){
        int val = a0 - k * b0;
        ans0[k] = C(k, val + k);
    }

    for (int k = 1; k <= a1 / b1; k++){
        int val = a1 - k * b1;
        ans1[k] = C(k, val + k);
    }

    int res = 0;

    ans0[0] = 1, ans1[0] = 1;

    for (int k = 1; k <= a0 / b0; k++){
        if (k > 1) add(res, (ans0[k] * ans1[k - 1]) % MOD);
        add(res, (ans0[k] * ans1[k]) % MOD);
    }

    for (int k = 1; k <= a1 / b1; k++){
       if (k > 1) add(res, (ans1[k] * ans0[k - 1]) % MOD);
       add(res, (ans1[k] * ans0[k]) % MOD);
    }
    cout << res << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    prep();

    int test = 1;
    // cin >> test;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}