# Pembahasan Soal Beda 0
Di pembahasan ini, misalkan saja $N = a_0 + a_1$.
## Subsoal 1
Perhatikan bahwa karena nilai $a_0, a_1$ kecil, lebih tepatnya $a_0 + a_1 \le 16$ maka kita dapat mencoba semua kemungkinan string dan memeriksa apakah string tersebut memenuhi syarat sesuai di soal. Kompleksitas: $O(N2^N)$

## Subsoal 2
Optimisasi brute force yang dibuat dengan membuat sebuah dynamic programming dengan $2$ state. $DP[idx][cnt0][last] =$ banyak cara membuat string sepanjang $idx$ jika index terakhirnya merupakan karakter $last$ dengan menggunakan karakter 0 sebanyak $cnt0$
Transisi dynamic programming dapat dibuat dengan menambahkan sebuah segmen karakter $0$ ataupun $1$ yang bersesuaian dengan persyaratan $b_0$ ataupun $b_1$.
- $DP[idx][cnt0][last] = DP[idx - i][cnt0 - i][!last], i \ge b_0$
- $DP[idx][cnt0][last] = DP[idx - i][cnt0][!last], i \ge b_1$

Jumlah state ada $O(N^2)$ dan transisi setiap state $O(N)$.

Kompleksitas: $O(N^3)$

## Subsoal 3
Solusi untuk subsoal 3 sama dengan solusi subsoal 2 dengan tambahan mempercepat transisi dengan menggunakan prefix sum. Perhatikan bahwa transisi pertama dapat dipercepat menggunakan diagonal prefix sum dan transisi kedua dapat dipercepat dengan menggunakan prefix sum biasa. Dengan itu, kompleksitas transisi akan berubah menjadi $O(1)$.

Kompleksitas: $O(N^2)$

## Subsoal 4
Perhatikan bahwa jika kita tahu bahwa ada $X$ segmen $0$ dan $Y$ segmen $1$, maka semua kemungkinan yang valid dapat kita hitung dengan mudah. Misalkan segmen-segmen $0$ panjangnya $X_1, X_2, ..., X_n$, maka banyak cara untuk mengisi segmen $0$ adalah $X_1 + X_2 + ... + X_n \le a_0$ dengan syarat $X_1, X_2, ..., X_n \ge b_0$. Persamaan ini dapat kita rubah menjadi $X_1 + X_2 + ... + X_n \le a_0 - b_0 \times n$. Hal yang serupa dapat kita lakukan untuk segmen $1$.

Untuk menyelesaikan persamaan dalam bentuk $A_1 + A_2 + ... + A_m \le c, A_1, A_2, ..., A_m \ge 0$ kita dapat memperhatikan nilai kombinasi yang akan dibuat.
Perhatikan bahwa banyak cara untuk menyelesaikan persamaan tersebut adalah:
$$\sum_{i = 0}^{c} \binom{m + i - 1}{m - 1}$$

Dengan menggunakan hockey stick identity, persamaan ini dapat disederhanakan menjadi
$$\binom{m + c}{m}$$

Dengan itu, kita dapat mencoba semua kemungkinan banyak segmen $0$ dan segmen $1$, lalu mencari banyak caranya berdasarkan setiap kombinasi segmen yang mungkin. Banyak kombinasi segmen yang mungkin adalah:
- $1⁢…10…0……1⁢…10…0$
- $0…01⁢…1……0…01⁢…1$
- $0…01⁢…1……1⁢…10…0$
- $1⁢…10…0……0…01⁢…1$

Nanti, jumlahkan saja semua kemungkinan dari banyak segmen $0$ dan $1$.

Kompleksitas: $O(N\text{log}_2(\text{mod}))$