---
---
# 🌱 Lời giải Mely Educational Contest 04 bài G :Vương quốc kẹo ngọt.

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:

###### 📋 Content:
[TOC]
____
## Nhận xét :label:
Đây là một bài quy hoạch động ở mức vận dụng, bạn cần có kiến thức nền về việc sử dụng các cấu trúc dữ liệu, bitmask và tối ưu hóa quy hoạch động bằng cấu trúc dữ liệu.
:bulb: Ta suy ra được công thức như sau :
>[color=green]
>- Gọi $dp[i][mask]$ là tổng số lượng dãy con tăng kết thúc tại $i$ và có các màu được biểu diễn là các bit $1$ tại các vị trí là số hiệu của các màu đó và bit tại vị trí là chỉ số màu $C_i$ **luôn bằng $1$**.
>- nhận thấy các số hiệu tối đa có thể có $2^{k} - 1$ trường hợp dãy con tăng có các trạng thái màu có trong dãy con đó (trừ trường hợp không có màu nào).
>- Từ cách gọi quy hoạch động như vậy ta thấy nếu $A_i > A_j$ $(i > j)$ thì ta có thể gắng các phần tử của dãy con tăng này vào trước $A_i$ nếu có $mask$ trạng thái miêu tả dãy con đó ta có thể bật bit (đánh số $1$) tại vị trí là số hiệu của $C_i$.
>- Từ đó ta có công thức quy hoạch động như sau nếu $A_i > A_j$ $(i > j)$ ta có số lượng dãy con tăng của từng trạng thái kết thúc tại $j$ là $dp[j][mask]$ việc cần làm là ta nối $A_i$ vào các dãy con tăng đó hay $dp[i][newmask] += dp[j][mask]$. Tại sao lại có **newmask** ? đó là việc bắt buộc bật bit tại vị trí là chỉ số màu $C_i$ hay nói dễ hiểu hơn là thêm màu $C_i$ vào trạng thái đó.
>
## Cải tiến :thumbsup:
+ Nhận thấy việc xét các trạng thái và so sánh để tính kết quả tốn mất độ phức tạp là $O(n^{2} * (2^{k} - 1))$ không đủ để accept bài này.
+ Ta bắt đầu nghĩ the hướng tối ưu bài quy hoạch động bằng cấu trúc dữ liệu.
+ Cũng dựa như trên nhưng ta lại nghĩ theo một hướng khác. Thay vì phải bó buộc bởi vị trí và muốn tìm một vị trí ta chỉ có duy nhất cách for trâu để tìm, liệu ta có cách nào để có thể **gom** lại để tính cùng **một lúc** hay không ?. Và nó ra đời, ta nhận xét cùng một trạng thái nhưng kết thúc có thể khác nhau, nhưng các kết thúc của dãy con tăng đó đều là các phần tử có giá trị **bé** hơn $A_i$.
+ Từ nhận xét trên, ta có thể suy ra một cách gọi khác như sau $dp[A_i][mask]$ là tổng số lượng dãy con tăng kết thúc có **giá trị là $A_i$** và có các màu được biểu diễn là các bit $1$ tại các vị trí là số hiệu của các màu đó và bit tại vị trí là chỉ số màu $C_i$ **luôn bằng $1$**.
+ Từ đó suy ra công thức quy hoạch động như sau:
>+ Để đếm số lượng dãy con tăng có kết thúc tại giá trị $A_i$ và có trạng thái các màu trong dãy con đó là $mask$ (lưu ý bit tại vị trí là số hiệu màu $C_i$ luôn bật). Ta có thể đếm tổng số lượng dãy con có kết thúc là các giá trị $<$ $A_i$ và có trạng thái tại tất cả các trạng thái.
>+ Ta có thể tính tổng bằng cách dùng Binary Index Tree.
>
## Code mẫu :bulb:
> **Time:** $O(nlog(n) * 2^{k-1})$
> **Space:** $O(n)$
> **Algo:** Dynamic programing , BIT , Bitwise.
> [color=lightgreen]
:::success
:::spoiler code của LeThanhMinh

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long pow_mod(long long a, long long b, long long m) {
     long long res = 1;
     while(b){
            res = res * (b & 1 ? a : 1) % m;
            a = a * a % m; b >>= 1;
     }
     return res;
}
long long GCD(ll a , ll b){
    while(b != 0 ){
         a = a % b;
         long long tmp = a;
         a = b;
         b = tmp;
    }
    return a;
}
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define ONBIT(x, i) ((x) | MASK(i))
const ll MAXN = 5e4 + 7;
const ll MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
int n , k;
ll bit[MAXN][200];
int a[MAXN], b[MAXN];
void update(int idx ,int mask ,ll val){
    for(  ;idx <= MAXN - 6 ; idx += idx & (-idx)){
        bit[idx][mask] += val;
        bit[idx][mask] %= MOD;
    }
}
ll get(int idx , int mask){
    ll res = 0;
    for( ; idx > 0 ; idx -= idx & (-idx)){
        res += bit[idx][mask];
        res %= MOD;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("new.inp" , "r" , stdin);
    // freopen("new.out" , "w" , stdout);
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i] >> b[i];
        a[i] ++;
        b[i] -- ;
    }
    ll res = 0;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 0 ; j < (1 << k) ; j ++){
            if(BIT(j , b[i]) == 0){
                int mask = ONBIT(j , b[i]);
                ll cur = get(a[i] - 1 , j);
                cur %= MOD;
                update(a[i] , mask , cur);
            }else{
                ll cur = get(a[i] - 1 , j);
                cur %= MOD;
                update(a[i] , j , cur);
            }
            if(j == 0){
                int mask = ONBIT(j , b[i]);
                update(a[i] , mask , 1);
            }
        }
    }
    cout << get(MAXN - 6 ,(1 << k) - 1) % MOD;
    return 0;
}

:::success