---
# System prepended metadata

title: 'Pusheen Contest 2023 #9'
tags: [CLA K22]

---

# Pusheen Contest 2023 #9

# Khoảng cách lớn nhất 
Cẩn thận tràn số.

# Chia kẹo
Đếm số bộ $x, y, z$ thỏa mãn 
$$
\begin{cases}
x+y+z = n \\
a|x, b|y, c|z
\end{cases}
$$

6 chia hết cho 3 $(6 \vdots 3)$ $\iff$ 3 chia hết 6 $(3|6)$.

sinh một bộ $x = x_1x_2\dots x_k, y = y_1y_2\dots y_m, z = \dots$
Tiến hành sinh từng chữ số của $x, y, z$, kiểm tra xem các chữ số này thỏa mãn chữ số tương ứng của tổng $n$ chưa rồi mới chuyển sang vị trí tiếp theo.


## Điều kiện $x+y+z = n$
Sinh theo chiều dọc - từng chữ số theo hàng đơn vị -> chục -> trăm-> ngàn ->.... Với mỗi vị trí, kiểm tra xem tổng có khớp với chữ số tại cùng hàng của $n$ ko, nếu thỏa mãn thì đem số nhớ qua để xét hàng tiếp theo.
![](https://hackmd.io/_uploads/ByUPmGGhn.png)

Gọi $dp[i][carry]$ là số cách để sinh $i$ chữ số thấp nhất của $x, y, z$ sao cho tổng khớp với $i$ chữ số thấp nhất của $n$, và số nhớ cho hàng tiếp theo là $carry$

```c++
ll dp[11][3];

ll DP(int i, int carry) {
    ll &res = dp[i][carry];
    if (res != -1) return res;
    if (i == 10) {
        if (carry == 0) return res = 1;
        else return res = 0;
    }
    for(x, 0, 9) for(y, 0, 9) for(z, 0, 9) {
        int digit = (x+y+z + carry) % 10;
        int newCarry = (x+y+z + carry) / 10;    
        if (digit == chữ số thứ i của N) {
            res += DP(i+1, newCarry);
        }
    }
    return res;
}

...
int main() {
    memset(dp, -1, sizeof dp);
    cout << DP(0, 0);
}
```

## Điều kiện chia hết cho $a, b, c$
 Thay vì sinh $x, y, z$ bất kì, thì ta sinh các bội của $a , b, c$ bằng cách tìm cách số $x', y', z'$ cho $x = x'.a, y = y'.b, z = z'.c$.
 
 ```c++
 ll dp[11][100];
 
 ll DP(int i, int carry) {
    ll &res = dp[i][carry];
    if (res != -1) return res;
    if (i == 10) {
        if (carry == 0) return res = 1;
        else return res = 0;
    }
    res = 0;
    for(x, 0, 9) for(y, 0, 9) for(z, 0, 9) {
        int sum = x*a+y*b+z*c + carry;
        int digit = sum% 10;
        int newCarry = sum / 10;    
        if (digit == chữ số thứ i của N) {
            res += DP(i+1, newCarry);
        }
    }
    return res;
}
 ```
 
Độ phức tạp: $O(10 \times 100 \times 10^3) = O(10^6)$

## Tối ưu ĐPT: Chuyển về hệ cơ số 2
 ```c++
 ll dp[32][70];
 
 ll DP(int i, int carry) {
    ll &res = dp[i][carry];
    if (res != -1) return res;
    if (i == 31) {
        if (carry == 0) return res = 1;
        else return res = 0;
    }
    res = 0;
    for(x, 0, 1) for(y, 0, 1) for(z, 0, 1) {
        int sum = x*a+y*b+z*c + carry;
        int digit = sum&1;
        int newCarry = sum>>1;    
        if (digit == bit thứ i của N) {
            res += DP(i+1, newCarry);
        }
    }
    return res;
}
 ```
 
 Độ phức tạp; $O(30 \times 70 \times 2^3) = O(16800)$
 
# Chọn đề thi 
Đếm số cách chọn $k$ số nguyên phân biệt thỏa mãn:
$$
\begin{cases}
x_1 + x_2+\dots + x_k = n\\
1 \le x_1 < x_2 < \dots < x_k \le n
\end{cases}
$$
![](https://hackmd.io/_uploads/BJDdsfGn2.png)

![](https://hackmd.io/_uploads/Hk9wozfh3.png)


## k = 2
```c++
ll dp[maxLen][maxK][2][2];


ll DP(int i, int carry, bool big0, bool big1) {
    if (i == -1) {
        if (carry == 0 && big0 && big1) return 1;
        else return 0;
    } 
    ll &res = dp[i][carry][big0][big1];
    if (res != -1) return res;
    res = 0;
    for(x, 0, 1) for(y, 0, 1) for(newCarry, 0, 2) {
        if (big1 == false && x > y) continue;
        int sum = x+y + newCarry;
        int digit = sum&1;
        if ((sum>>1) == carry && digit == bit thứ i của N) {    
            res += DP(i-1, newCarry, big0|x, big1|(x < y));        
        }
    }
    return res;
}

int main() {
    memset(dp, -1, sizeof dp);
    cout << DP(32, 0, 0, 0);
}
```

## k = 5 (thực tế có thể chạy tới k <= 8)
```c++
#define MASK(s) ((1ll)<<(s))
#define BIT(s, i) (((s)>>(i))&1)
ll dp[maxLen][maxK][MASK(maxK)];

int check(int bigger, int digits) {
    int ans = 0;
    FOR(i, 0, k-1) {
        int last = i == 0 ? 0 : BIT(digits, i-1);
        if (BIT(bigger, i) == 0 && last > BIT(digits, i)) return -1;
        else if (BIT(bigger, i) || last < BIT(digits, i))
            ans |= MASK(i);
    } 
    return ans;
}

ll DP(int i, int carry, int bigger) {
    if (i == -1) {
        if (carry == 0 && bigger == MASK(maxK)-1) return 1;
        else return 0;
    } 
    ll &res = dp[i][carry][bigger];
    if (res != -1) return res;
    res = 0;
    for(digits, 0, MASK(k)-1) for(newCarry, 0, k) {
        int newBigger = check(bigger, digits);
        if (newBigger == -1) continue;
        int sum = __builtin_popcount(digits) + newCarry;
        int digit = sum&1;
        if ((sum>>1) == carry && digit == bit thứ i của N) {    
            res += DP(i-1, newCarry, newBigger);        
        }
    }
    return res;
}

int main() {
    memset(dp, -1, sizeof dp);
    cout << DP(32, 0, 0, 0);
}
```

Độ phức tạp: $O(32 \times (k \times 2^k)^2)$ 

Code tham khảo: https://ideone.com/zBMqUp
Code tối ưu hơn: https://ideone.com/4lQ51w

# Làm đề thi - Lê Minh Hoàng
Đếm số cách chọn $k (k \le 10)$ số nguyên phân biệt thỏa mãn:
$$
\begin{cases}
x_1 + x_2+\dots + x_k = n\\
1 \le x_1 < x_2 < \dots < x_k \le n
\end{cases}
$$

![](https://hackmd.io/_uploads/HJ0gU7fh3.png)

Gọi mảng $y$ sao cho $x_i = y_i + y_{i+1} + \dots + y_k$ (xem $x$ như mảng cộng dồn của $y$. Bài toán trở thành tìm mảng $y$ sao cho: 
$$
\begin{cases}
y_1 + 2 \times y_2 + \dots + (k-1)\times y_{k-1} +  k \times y_k = n\\
1 \le y_i 
\end{cases}
$$

Biến đổi biểu thức về dạng đồ thị, ta nhận thấy số nghiệm của bài toán là số đường đi từ $0$ đến $k$ độ dài (tổng trọng số các cạnh đi qua) là $n$. Với $y_i$ tương ứng với số lần thăm đỉnh $i$ của đường đi.
![](https://hackmd.io/_uploads/B1D5vQM33.png)

Bài toán trở thành đếm số đường đi độ dài $n$ từ $0$ đến $k$ trên đồ thị, ta tách các cạnh có trọng số $x > 1$ thành $x$ cạnh nhỏ có trọng số $1$.
![](https://hackmd.io/_uploads/r19i_Xf2h.png)

Đồ thị mới bao gồm $k^2 \approx 55$ đỉnh và khoảng $4k^2$ cạnh. Ta có thể dễ dàng giải quyết tương tự bài [Walk](https://claoj.edu.vn/problem/atcoder_dp_walk).

Độ phức tạp: $O((k^2)^3 \log n)$

Code tham khảo: https://ideone.com/8H06bR

## Xếp tượng 

- Xoay bảng 45 độ, khi đó đường chéo trở thành hàng và cột của bàn cờ mới.
- Việc đặt những quân tượng ở hàng chẵn sẽ chỉ làm ảnh hưởng đến những quân tượng ở hàng chẵn, tương tự với hàng lẻ.

![](https://hackmd.io/_uploads/r1D4m6TT2.png)

Gọi $dp[i][j]$ là số cách đặt $j$ quân tượng vào $i$ hàng đầu tiên,chuyển trạng thái từ hàng $i-2$. 
- Số lượng cột trống tại hàng $i$: $i-j$
$$
dp[i][j] += dp[i-2][j-1] * 2 * 
$$







