# 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.

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$

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$.

 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

 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}
$$


## k = 2

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)

#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}
$$


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.

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$.

Đồ 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ẻ.


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 *
$$