---
tags: VNOJ, THT, DP, Math, Brute-force, Space Optimization, Time Optimization, Branch-and-Bound, SPyofgame, matchamachiato, eggdacoder2006, DeMen100ns, nothere
title: 🌱 Tin học trẻ 2021 - Vòng Khu vực - Bảng C - Số hoàn hảo
author: Editorial-Slayers Team
license: Public domain
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🌱 Tin học trẻ 2021 - Vòng Khu vực - Bảng C - Số hoàn hảo}$

-----

###### 🔗 Link: [https://oj.vnoi.info/problem/tht21_kvc_pnum](https://oj.vnoi.info/problem/tht21_kvc_pnum)
###### 📌 Tags: `DP`, `Math`, `Brute-force`, `Space Optimization`, `Time Optimization`, `Branch-and-Bound`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: @eggdacoder2006, @matchamachiato, @DeMen100ns, [@Nguyễn Nam](https://www.facebook.com/nguyennam.2018), @Melonade
###### 🛠 Work: 8h
###### 📋 Content:

[TOC]

-----
## Bổ đề và chứng minh bổ đề

==**Mệnh đề:** Mọi dãy độ dài chẵn $n$ gồm các số nguyên từ $1$ đến $k\ (k \leq n)$ có tổng là $2n$ thì luôn chia được thành $2$ dãy có tổng bằng nhau và bằng $n$==

Gọi tập đang xét là $x_1, x_2, \dots, x_n$

Xét dãy gồm các phần tử bằng nhau

- Vì $n$ là một số chẵn nên ta có thể chia làm $2$ phần có tổng bằng nhau, mỗi phần gồm $\frac{n}{2}$ phần tử

Ngược lại, tồn tại $2$ phần tử là $x_1 \neq x_2$

- Đặt $\begin{cases}
S_1 = x_1\\
S_2 = x_1 + x_2\\
\dots\\
S_{n-1} = x_1 + x_2 + \dots + x_{n-1}
\end{cases}$
- Trường hợp tồn tại $p$ để $S_p = n$, ta có thể chia dãy làm $\{x_1, x_2, \dots, x_p\}$ và $\{x_{p+1}, x_{p+2}, \dots, x_n\}$
- Trường hợp tồn tại $p < q$ để $S_p \equiv S_q \pmod {n}$, ta có thể chia dãy làm $\{x_{p+1}, x_{p+2}, \dots, x_q\}$ và $\{x_1, x_2, \dots, x_p, x_{q+1}, x_{q+2}, \dots, x_n\}$
- Trường hợp còn lại, ta có $\{S_1, S_2, \dots, S_{n-1}\} = \{1, 2, \dots, n-1\}$
- Mà ta lại có $x_1 \neq x_2$ nên khi thay thế $S_1 = x_1$ bởi $x_2$ thì sẽ tồn tại một cặp $(p, q)$ sao cho $S_p \equiv S_q \pmod {n}$. Sau đó ta lại chia dãy như trên
- Vậy ta có điều phải chứng minh :thumbsup:

-----
## Thuật toán quy hoạch động

Áp dụng bổ đề vào bài toán ta có điều kiện $2$ luôn thỏa với mọi dãy thỏa điều kiện $1$ cho trước.

Vậy bài toán của ta là đếm số dãy $a_1, a_2, \dots, a_n$ với $1 \leq a_i \leq k$ và $\overset{p_i + 9}{\underset{k = p_i}{\Large \Sigma}} a_k = 20$ với mọi $1 \leq i \leq m$.

Xét đến $m = 5$, ta có hàm quy hoạch động $f[i][s_1][s_2][s_3][s_4][s_5]$ là số cách chọn dãy xét đến vị trí $[i]$ và tổng của $5$ đoạn con được chọn hiện tại lần lượt là $s_1, s_2, s_3, s_4,s_5$.

Để cho tiện ta sẽ gọi một dãy rỗng là một cách chọn, hay cơ sở quy hoạch động là $f[0][0][0][0][0][0] = 1$.

Ở mỗi bước, ta thử từng trường hợp điền chữ số vào vị trí thứ $i$ là các số nguyên từ $1 \dots k$, ta có:

- $f[i][s_1][s_2][s_3][s_4][s_5] \rightarrow f[i + 1][t_1][t_2][t_3][t_4][t_5]$
- Trong đó $\begin{cases}
t_x = s_x + a_i & \text{khi } p_i \leq i \leq p_i + 9\\
t_x = s_x & \text{mọi trường hợp khác }
\end{cases}$

Đặt $v_x = \begin{cases}
20 & \text{khi } p_i \leq i \leq p_i + 9\\
0 & \text{mọi trường hợp khác }
\end{cases}$, kết quả bài toán là $f[n][v_1][v_2][v_3][v_4][v_5]$.

Độ phức tạp cách quy hoạch động này là $O(nk \times 21^m)$.

-----

Không mất tính tổng quát với mọi cách chọn dãy như trên ta đều có thể giảm mỗi phần tử $a_i$ đi một đơn vị.

$\Large \Rightarrow$ Bài toán trở thành đếm số dãy $a_1, a_2, \dots, a_n$ với $0 \leq a_i < k$ và $\overset{p_i + 9}{\underset{k = p_i}{\Large \Sigma}} a_k = 10$ với mọi $1 \leq i \leq m$.

Vậy lần này, độ phức tạp quy hoạch động chỉ còn $O(nk \times 11^m)$.

**Ưu điểm:** Gọn, dễ code, dễ debug, dễ tính.

-----
### Iterative Code

> **Time:** $O(nk \times 11^m)$
> **Space:** $O(n \times 11^m)$
> **Algo:** DP, Math, Brute-force, Space Optimization, Time Optimization
> [color=lightgreen]

:::success
:::spoiler DeMen100ns Code

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;
int dp[105][11][11][11][11][11], l[105], r[105], sum[105];
int n, k, m, D;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m >> D;
    for(int i = 1; i <= m; i++)
    {
        cin >> l[i];
        r[i] = l[i] + 9;
        sum[i] = 10;
    }
    dp[0][0][0][0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    for(int sum1 = 0; sum1 <= sum[1]; sum1++)
    for(int sum2 = 0; sum2 <= sum[2]; sum2++)
    for(int sum3 = 0; sum3 <= sum[3]; sum3++)
    for(int sum4 = 0; sum4 <= sum[4]; sum4++)
    for(int sum5 = 0; sum5 <= sum[5]; sum5++)
    for(int digit = 0; digit <= k-1; digit++)
    {
        int tmp1 = sum1 + digit*(l[1] <= i && i <= r[1]);
        int tmp2 = sum2 + digit*(l[2] <= i && i <= r[2]);
        int tmp3 = sum3 + digit*(l[3] <= i && i <= r[3]);
        int tmp4 = sum4 + digit*(l[4] <= i && i <= r[4]);
        int tmp5 = sum5 + digit*(l[5] <= i && i <= r[5]);
        if(max({tmp1, tmp2, tmp3, tmp4, tmp5}) > 10) break;
        dp[i][tmp1][tmp2][tmp3][tmp4][tmp5] += dp[i-1][sum1][sum2][sum3][sum4][sum5];
        dp[i][tmp1][tmp2][tmp3][tmp4][tmp5] %= D;
    }
    cout << dp[n][sum[1]][sum[2]][sum[3]][sum[4]][sum[5]];
}

:::

> **Time:** $O(nk \times 11^m)$
> **Space:** $O(11^m)$
> **Algo:** DP, Math, Brute-force, Space Optimization, Time Optimization
> [color=lightgreen]

:::success
:::spoiler SPyofgame Code

#include <iostream>
#include <cstring>

using namespace std;

int c[2][11][11][11][11][11];
int f[2][11][11][11][11][11];
int l[5];
int r[5];
int s[5];
int main()
{
    /// Input
    int n, k, m, D;
    cin >> n >> k >> m >> D;
    for (int i = 0; i < m; ++i)
    {
        cin >> l[i];
        r[i] = l[i] + 9;
        s[i] = 10;
    }

    /// Initialization
    memset(c, 0, sizeof(c));
    memset(f[0], 0, sizeof(0));
    f[0 & 1][0][0][0][0][0] = 1;
    for (int i = m; i < 5; ++i)
        l[i] = r[i] = s[i] = 0;

    /// Solving
    for (int i = 1, cur = 1, pre = 0; i <= n; ++i, cur ^= 1, pre ^= 1)
    {
        int f0 = (l[0] <= i) && (i <= r[0]); /// Check if this position is in the first  set
        int f1 = (l[1] <= i) && (i <= r[1]); /// Check if this position is in the second set
        int f2 = (l[2] <= i) && (i <= r[2]); /// Check if this position is in the third  set
        int f3 = (l[3] <= i) && (i <= r[3]); /// Check if this position is in the fourth set
        int f4 = (l[4] <= i) && (i <= r[4]); /// Check if this position is in the last   set
        for (int d = 0; d < k; ++d)
        {
            for (int s0 = s[0], t0 = s0 - f0 * d; t0 >= 0; --t0, --s0) /// First  set
            for (int s1 = s[1], t1 = s1 - f1 * d; t1 >= 0; --t1, --s1) /// Second set
            for (int s2 = s[2], t2 = s2 - f2 * d; t2 >= 0; --t2, --s2) /// Third  set
            for (int s3 = s[3], t3 = s3 - f3 * d; t3 >= 0; --t3, --s3) /// Fourth set
            for (int s4 = s[4], t4 = s4 - f4 * d; t4 >= 0; --t4, --s4) /// Last   set
            {  
                int &p = c[cur][s0][s1][s2][s3][s4]; /// Check whether this state is visited
                int &r = f[cur][s0][s1][s2][s3][s4]; /// Value of curent state
                int &v = f[pre][t0][t1][t2][t3][t4]; /// Value of previous state
                if (p != i) p = i, r &= 0; /// Re-init this state as 0
                if ((r += v) >= D) r -= D; /// Adding previous value to current state, under modulo
            }
        }
    }

    /// Output
    cout << f[n & 1][s[0]][s[1]][s[2]][s[3]][s[4]];
    return 0;
}

:::

-----
## Thuật toán đệ quy có nhớ

Tương tự với thuật quy hoạch động, ta đếm số dãy $a_1, a_2, \dots, a_n$ với $0 \leq a_i < k$ và $\overset{p_i + 9}{\underset{k = p_i}{\Large \Sigma}} a_k = 10$ với mọi $1 \leq i \leq m$.

Gọi $f(x, s[m])$ là số cách chọn dãy bắt đầu từ vị trí $[i]$ và tổng của $m$ đoạn con còn lại hiện tại lần lượt là $s[1], s[2], s[3], s[4],\dots, s[m]$.

Tuy rằng ta có thể làm tương tự như trên để đạt cùng độ phức tạp, tuy nhiên ta có thể dùng `C++std::unordered_map` để chỉ những dãy thỏa mãn mới được xét đến và hạn chế các nhánh không dùng đến.

Ta định nghĩa:
- $f(x - 1, t[m])$ là trạng thái tiếp theo ta sẽ xét;
- $ins[x]$ là tập chứa số thứ tự các đoạn $[p_i, p_i + 9]$ mà $x$ nằm trong đoạn đó;
- $rmv[x]$ là tập tương tự như $ins[x]$ nhưng có ý nghĩa là vị trí tiếp theo mà tổng đang xét không còn nằm trong đoạn cần xét.

Ta có kết quả bài toán là $f(n, v[m])$, trong đó:
$v_x = \begin{cases}
20 & \text{khi } p_i \leq i \leq p_i + 9\\
0 & \text{mọi trường hợp khác }
\end{cases}$

Khi đã duyệt hết các giá trị, thì ta có: $f(0, s[m]) = \begin{cases}
1 & \text{khi } s_x = 0\ \forall\ p_i \leq i \leq p_i + 9\\
0 & \text{mọi trường hợp khác, hoặc luôn không tồn tại nếu ta dùng } rmv[x]
\end{cases}$

Ngược lại, tại các vị trí đang xét từ $n$ trở xuống, mỗi khi ta thử duyệt một chữ số $d$ cho vào vị trí hiện tại:
- Xét với mọi $i \in ins[x]$ và $j \in rmv[x]$.
- Ta kiêm tra nếu tồn tại $s_j - d \neq 0$ thì ta sẽ không điền $d$ vì tổng này còn thiếu để thỏa mãn.
- Ta kiểm tra nếu tồn tại $s_i - d < 0$ thì ta sẽ không điền số $d$ vì lấy vượt quá giá trị tổng.

Mặc dù ta có thể thêm nhánh cận hơn nữa, nhưng với bài này thì không cần thiết vì giới hạn quá nhỏ, thậm chí còn làm giảm tốc độ do tăng hằng số lên.

Độ phức tạp cách trên là $O((k + 10m) \times |S|)$ $=$ $O\left(n(k + 10m) C_{19}^{10}\right)$ với $S$ là tập các trạng thái $(n, s[5])$ phân biệt có thể xảy ra.

**Ưu điểm:** Cực kì nhanh, xét rất ít trường hợp, dễ thay đổi cho các trường hợp tổng quát hơn.

-----
### Recursive Code

> **Time:** $O(nk \times 11^m)$
> **Space:** $O(n \times 11^m)$
> **Algo:** DP, Math, Brute-force, Space Optimization, Time Optimization
> [color=lightgreen]

:::success
:::spoiler Duyle Code

#include <bits/stdc++.h>

using namespace std;

const long long oo = 1e18;
const long long N = 2e5 + 5;

int dp[55][12][12][12][12][12], p[6], m, k, d, n;
vector <int> vi(5, 0);

int solve(long long pos)
{
    if (pos == n)
    {
        for (int &u: vi) if (u != 10) return 0;
        return 1;
    }
    int &ans = dp[pos][vi[0]][vi[1]][vi[2]][vi[3]][vi[4]];
    if (ans != -1) return ans;
    ans = 0;
    for(int i = 0; i < k; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(pos + 1 >= p[j] && pos + 1 <= p[j] + 9) vi[j] += i;
        }
        if (*max_element(vi.begin(), vi.end()) <= 10)
        {
            ans = (ans + solve(pos + 1))%d;
        }
        for(int j = 0; j < m; j++)
        {
            if (pos + 1 >= p[j] && pos + 1 <= p[j] + 9) vi[j] -= i;
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> m >> d;
    for(int i = 0; i < m; i++) cin >> p[i];
    memset(dp, -1, sizeof dp);
    for (int i = m; i < 5; i++) vi[i] = 10;
    cout << solve(0);
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

:::

> For $S$ is the set of all possible state $(n, s[5])$
> **Space:** $O(|S|)$ $=$ $O\left(n \times C_{19}^{10} \right)$
> **Time:** $O((k + 10m) \times O(space))$
> **Algo:** DP, Math, Brute-force, Space Optimization, Time Optimization, Branch-and-Bound
> [color=lightgreen]

:::success
:::spoiler SPyofgame Code

#include <unordered_map>
#include <iostream>
#include <vector>

using namespace std;

constexpr int pw11[5] = {1, 11, 121, 1331, 14641};
constexpr int LIM = 55;

int n, k, m, D;
int p[5];
unordered_map<int, int> dp[LIM];
vector<int> rmv[LIM], ins[LIM];
int magic(int pos, int s[5]) /// Current state
{
    if (pos == 0) return 1; /// Base state

    int code = 0;
    for (int i = 0; i < m; ++i) code += s[i] * pw11[i]; /// getting the hash code
    if (dp[pos].count(code)) return dp[pos][code]; /// getting the value of current state
    int &res = dp[pos][code] = 0;

    int t[5] = {s[0], s[1], s[2], s[3], s[4]};
    for (int d = 0; d < k; ++d) /// Try each number 0, 1, ..., k - 1
    {
        for (int i : ins[pos]) if (s[i] < d) return res; /// this digit is invalid, take more sum than needed
        for (int i : ins[pos]) t[i] = s[i] - d;          /// select this digit
        for (int i : rmv[pos]) if (t[i] != 0) goto skip; /// this digit is invalid, take less sum than needed
        res += magic(pos - 1, t); /// move to next state
        if (res >= D) res -= D; /// taking the modulo
        skip: {}
    }

    return res; /// Return result
}

int main ()
{
    cin >> n >> k >> m >> D;
    int base[5] = {0, 0, 0, 0, 0};
    for (int i = 0; i < m; ++i)
    {
        base[i] = 10; /// select up to sum = 10
        cin >> p[i];
        rmv[p[i]].push_back(i); /// The fist moment the sum will no longer for the sum at [i]
        for (int j = p[i]; j <= p[i] + 9; ++j) ins[j].push_back(i); /// The range of moment where we do care for the sum at [i]
    }

    cout << magic(n, base);
    return 0;
}

:::

-----
### Bonus
* Bạn có thể giải bài toán với $m = 0$ và $n$ lớn không?
* Bạn có thể giải bài với $O(f(x) \times 10^m)$ thay cho $O(f(x) \times 11^m)$ với $O(f(x))$ là độ phức tạp cho phương pháp bạn chọn không?