# Biến đổi :
- Không mất tính tổng quát, ta sẽ biến đổi lại bài toán để dễ dàng thực hiện hơn :
$$
x_0 + x_1 + \dots + x_{k - 1} = n$$
$$x_0 > x_1 > \dots > x_{k - 1} > 0$$
- Thay vì sử dụng hệ thập phân để giải, ta sẽ sử dụng hệ nhị phân để dễ dàng cho lời giải hơn.
# Lời giải :
- Tới đây, ta sẽ quy hoạch động chữ số cho cả $k$ số ở hệ nhị phân.
- Ta sẽ xử lý từng điều kiện riêng của bài toán.
- Với điều kiện $1$ : $x_0 + x_1 + \dots + x_{k - 1} =n$
- Ta sẽ tư duy theo hướng "nợ" và "trả".
- Giả sử $n= 101$ (Vị trí từ phải sang trái).
- Khi xét tại vị trí $2 \to$ có bit $1$ thì phương trình đang "nợ" $1$ bit.
- Khi xét tại vị trí $1 \to$ có bit $0$ thì phương trình đang "nợ" $2$ bit.
- Khi xét tại vị trí $0 \to$ có bit $1$ thì phương trình đang "nợ" $5$ bit.
- Tại sao lại như vậy ? Bởi vì, nếu đang nợ tại bit thứ $i$ là $1$ thì sang $i - 1$ ta cần phải "trả" $2$ bit mới đủ để bù lại.
- Do đó nếu tại vị trí $i$, nếu là $1$ ta sẽ cộng $1$ vào khoảng "nợ". Và khi đi qua $i - 1$ khoảng "nợ" đó $\times2$ (Như trên ví dụ).
- $\to$ Qua nhận xét trên, gọi $t$ là khoảng "nợ" hiện tại khi xét tới vị trí $i$. Bài toán chỉ hợp lệ $⇔$ $t \le k \times(i + 1)$.
- Với điều kiện $2$ : $x_0 > x_1 > \dots > x_{k -1} > 0$.
- Thêm một chiều nhị phân $mask$ để quản lý $i$ đã lớn hơn $i + 1$ hay chưa.
- Nếu tại $mask_{k-1} = 1$ có nghĩa $x_{k-1} > 0$ thì mọi số phía trước đều sẽ $> 0$.
- Tóm gọn lại :
- Gọi $dp[i][j][mask]$ số cách khi xét tới vị trí thứ $i$, đang "nợ" $j$ bit và $mask$ quản lý lớn nhỏ.
- Bài toán có kết quả khi đến cuối : $j = 0$.
- Cách chuyển trạng thái :
```C++
/// Cộng thêm, nếu tại vị trí pos là 1
int _new = j + (n >> pos & 1);
FOR(sub, 0, (1 << k) - 1){
int t = __builtin_popcount(sub);
int to = 0;
bool check = 1;
/// Đặt bit cho cả k số, chuyển trạng thái của mask
FOR(i, 0, k - 1){
int x = (sub >> i & 1), y = (sub >> (i + 1) & 1);
if(x > y){
to ^= (1 << i);
}
else if(x < y){
int p = (mask >> i & 1);
check &= (p == 1);
}
}
/// t ở đây là số bit được "trả" (ít hơn số nợ)
/// khi đó nếu đang nợ j thì qua sẽ nợ 2 * (j - t) cho vị trí kế
if(t <= _new && check){
ans += calc(pos - 1, 2 * (_new - t), mask | to);
}
}
```
- Tối đa ta chỉ có thể nợ 150 bit, điều này có thể tự chứng minh.
- Độ phức tạp : $O(150.log_2(n).2^{2k})$.
hiepsimauhong
Created at
0 likes