# DELETE

## SUBTACK
**SUBTACK 1:** $n \le 20$
**SUBTACK 2:** $n \le 10^3$
**SUBTACK 3:** $n \le 10^6$

## SOLUTION CỦA DELETE

### SUB 1:

Sử dụng **bitmask** để vét tất cả các trường hợp.

:::success
:::spoiler CODE MẪU

#include <bits/stdc++.h>

#define bit(mask, i) ((mask >> i) & 1)
#define BIT(i) (1 << i)

using namespace std;

const int maxn = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, a[maxn], ans = 0;

bool check(int mask)
{
    vector<int> v;
    for (int i = 0; i < n; i++) if (bit(mask, i)) v.push_back(a[i]);
    if (v.size() < 3) return 0;
    if (v.front() != 1 || v.back() != 3) return 0;
    for (int i = 1; i < v.size() - 1; i++) if (v[i] != 2) return 0;
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("DELETE.INP", "r", stdin);
    freopen("DELETE_TRAU.OUT", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int mask = 0; mask < BIT(n); mask++)
    {
        ans += check(mask);
        ans %= MOD;
    }
    cout << ans;
}

:::

**ĐỘ PHỨC TẠP LÀ:** $O(2^n)$

### SUB 2:

Sử dụng quy hoạch động để tối ưu.

Gọi $dp[i]$ là số cách chọn dãy thỏa mãn yêu cầu kết thúc tại $i$

$\Rightarrow$ Kết quả của bài toán là tổng các $dp[i]$ với $a[i] = 3$

Ban đầu khởi tạo các giá trị $dp[i] = 0$ với mọi $i$ thỏa mãn $1 \le i \le n$

Công thức truy hồi:
- Theo đề ta có: Nếu $a[i] = 1$ thì phần tử thứ $i$ chỉ được xuất hiện 1 lần ở đầu dãy. Nói cách khác, chả cả phần tử nào đứng trước phần tử thứ $i$ được vì $i$ là thằng đầu tiên $\Rightarrow$ $dp[i] = 1$ với $a[i] = 1$
- Tiếp theo, nếu $a[i] = 2$ thì phần tử thứ $i$ có thể nối với phần tử có giá trị $1$ hoặc các phần tử có giá trị $2$ $\Rightarrow$ $dp[i] = dp[i] + dp[j]$ với $a[i] = 2$ và $a[j] = 1$ hoặc $a[j] = 2$
- Cuối cùng, nếu $a[i] = 3$ thì phần tử thứ $i$ chỉ có thể nối với phần tử có giá trị $2$ để tạo nên dãy đúng $\Rightarrow dp[i] = dp[i] + dp[j]$ với $a[i] = 3$ và $a[j] = 2$

:::success
:::spoiler CODE MẪU

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, a[maxn], dp[maxn], ans = 0;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("DELETE.INP", "r", stdin);
    freopen("DELETE_TRAU2.OUT", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 1)
        {
            dp[i] = 1;
            continue;
        }
        for (int j = 1; j < i; j++)
        {
            if (a[i] == 2 && a[i] >= a[j]) dp[i] += dp[j], dp[i] %= MOD;
            if (a[i] == 3 && a[j] == 2) dp[i] += dp[j], dp[i] %= MOD;
        }
    }
    for (int i = 1; i <= n; i++) if (a[i] == 3) ans += dp[i], ans %= MOD;
    cout << ans;
}

:::

**ĐỘ PHÚC TẠP:** $O(n^2)$

### SUB 3:

Vẫn là quy hoạch động nhưng chúng ta sẽ tìm cách tối ưu chiều.

Để ý rằng, với mỗi $dp[i]$ chúng ta gọi ở trên chúng ta chỉ cần tìm $1$ giá trị cụ thể rồi cộng vô đáp án.

Ở subtack cuối này chúng ta sẽ gọi $dp[i]$ là số lượng dãy có phần tử kết thúc là giá trị $i$.

Với cách gọi như vậy thì đáp án của bài toán sẽ là $dp[3]$ (số dãy có phần tử kết thúc mang giá trị $3$)

Công thức truy hồi:
- Nếu $a[i] = 1$ thì giá trị này sẽ tạo ra thêm 1 dãy kết thúc với giá trị $1$ $\Rightarrow$ $dp[1] = dp[1] + 1$
- Nếu $a[i] = 2$ thì giá trị này sẽ nối với giá trị $1$ để tạo ra thêm $1$ dãy có chiều dài bằng $2$ và giá trị bắt đầu là $1$ và giá trị kết thúc là $2$. Hoặc nối với phần tử có giá trị là $2$ để tạo ra dãy mới vẫn thỏa mãn yêu cầu đề bài $\Rightarrow$ $dp[2] = dp[2] + dp[1] + dp[2]$
- Nếu $a[i] = 3$ thì giá trị này phải đi với phần tử kết thúc có giá trị $2$ $\Rightarrow dp[3] = dp[3] + dp[2]$

:::success
:::spoiler CODE MẪU

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int n, dp[4];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("DELETE.INP", "r", stdin);
    freopen("DELETE.OUT", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == 1) dp[1]++;
        else if (x == 2)
        {
            dp[2] += dp[1] + dp[2];
            dp[2] %= MOD;
        }
        else dp[3] += dp[2], dp[3] %= MOD;
    }
    cout << dp[3];
}

:::