# Pusheen Contest 2023 #6
###### tags: `CLA K22`

## Matching

### bitmask
Cách biểu diễn một chuỗi nhị phân thành một số nguyên thập phân.
VD:
- $101_2 \to 2^2 + 2^0 = 5_{10}$
- $1100_2 \to 2^3+2^2 = 12_{10}$

#### Phép xử lí bit
1. Phép and: `a&b`
$$
\begin{matrix}
5= & 0101\\
12= & 1100\\
& ---\\
4= & 0100
\end{matrix}
$$
`5&12 = 4`

2. Phép or: `a|b`
$$
\begin{matrix}
5= & 0101\\
12= & 1100\\
& ---\\
13= & 1101
\end{matrix}
$$
`5|12 = 13`

3. Phép xor: `a^b`
Khác nhau thì ra $1$, giống nhau thì ra $0$. Cộng không nhớ
$$
\begin{matrix}
5= & 0101\\
12= & 1100\\
& ---\\
9= & 1001
\end{matrix}
$$
`=> 5^12 = 9`

4. Phép cộng trừ:
Tương tự cộng trừ trong hệ nhị phân
Xét $5+12$
$$
\begin{matrix}
5= & 0101\\
12= & 1100\\
& ---\\
17= & 10001
\end{matrix}
$$

5. Phép dịch bit
Dịch phải: `S>>i`, loại bỏ $i$ bit thấp nhất. Tương tự với `S / pow(2, i)`. VD: $S = 1101_2$, $S>>2 = 11_2$
Dịch trái `S<<i`, thêm vào $i$ bit 0 vào đầu dãy. Tương tự với `S * pow(2, i)`. VD: $S = 1101_2$, $S<<2 = 110100_2$

#### Biểu diễn tập hợp
Với một tập hợp $n$ phần tử $a = \{a_1, a_2, \dots, a_n\}$, khi muốn biểu diễn một tập con của a, ta có thể dùng một dãy nhị phân. Với mỗi vị trí $i$ trên dãy, nếu bit đó là $0$ thì phần tử đó không thuộc tập con, ngược lại nếu bit là $1$ thì phần tử đó thuộc tập con.

VD: $A = \{1, 2, 3, 4, 5\}$. Khi muốn biểu diễn tập $\{3, 5\}$, ta có thể biểu diễn bằng một dãy nhị phân $5$ phần tử: $00101$. Khi chuyển dãy này sang hệ thập phân, ta được $00101_2 = 2^2 + 2^0 = 5_{10}$.

Số lượng tập con của một tập hợp $n$ phần tử là $2^n$ tập hợp và có thể được biểu diễn bằng các bitmask từ $0$ đến $2^n-1$. Với $0$ biểu diễn tập rỗng, và $2^n-1 = 1111\dots 1$ biểu diễn tập hợp ban đầu.

#### Một số thao tác thường dùng.

1. Kiểm tra tính chẵn lẻ
Số chẵn khi bit đầu tiên có giá trị là $0$.
Sô lẻ khi bit đầu tiên có giá trị là $1$.
Cú pháp: `S&1`

$$
101\&1 = 1
$$

2. Kiểm tra bit thứ $i$ của một bitmask $S$

#define BIT(S, i) (((S)>>(i))&1)

Nếu bit thứ $i$ của $S$ là 1 thì kết quả trả về 1, ngược lại trả về $0$

3. Lấy giá trị $2^i$ trong $O(1)$/ Tạo một dãy nhị phân có duy nhất bit ở vị trí $i$

#define MASK(i) ((1ll)<<(i))

4. Đếm số bit 1 trong mask
`__builtin_popcount(S)` hoặc `__builtin_popcountll(S)`

### Lời giải
Gọi $dp[i][S]$ là số cách ghép được khi xét đến bạn nam thứ $i$, và $S$ là tập các bạn nữ chưa được ghép.

Khi xét đến bạn nam thứ $i$, ta sẽ thử ghép bạn này với các bạn nữ chưa được ghép.

#include <bits/stdc++.h>
using namespace std;

#define BIT(S, i) (((S)>>(i))&1)
#define MASK(i) ((1ll)<<(i))

const int N = 23;
int n;
int dp[N][MASK(21)];
const int MOD = 1e9+7;
int a[N];

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) 
	for(int j = 1; j <= n; ++j) {
		int x; cin >> x;
		if (x) a[i] |= MASK(j-1); 
	}
	
	memset(dp, 0, sizeof dp);
	dp[1][MASK(n)-1] = 1;
	for(int i = 1; i <= n; ++i) 
	for(int S = 0; S < MASK(n); ++S) if (dp[i][S]) {
	    add(dp[i+1][S], dp[i][S]);
	    // cout << i << ' ' << S << ' ' << dp[i][S] << '\n';
	    for(int tmp = S&a[i], j; tmp > 0; tmp ^= MASK(j)) {
	    	j = __builtin_ctz(tmp);
	    	add(dp[i+1][S^MASK(j)], dp[i][S]);
	    }
	}
    
	cout << dp[n+1][0];
	return 0;
}

#### Tối ưu cài đặt
Thay vì duyệt từng bạn nữ $j$ rồi kiểm tra có nằm trong mask không và có hòa hợp với bạn nam $i$ không, ta lưu $a[i]$ dưới dạng một bitmask, và dùng toán tử $\&$ với S trong hàm $dp$, khi đó ta được một bitmask mới gồm các bit 1 có trong cả $a[i]$ và $S$ đang xét, từ đó ta chỉ cần duyệt các bit 1 trong bitmask mới này.

#### Duyệt các bit 1 trong một mask (bỏ qua các bit 0)

for(int tmp = mask, i; tmp > 0; tmp ^= MASK(i)) {
    i = __builtin_ctz(mask);
    // your code
}

Tham khảo: https://vnoi.info/wiki/translate/topcoder/fun-with-bits.md

## Idependent Set
Gọi $dp[u][c]$ là số cách tô cây con gốc $u$ hợp lệ sao cho đỉnh $u$ được tô màu $c$.

const int MOD = 1e9+7;
void merge(int cur, int child) {
    dp[cur][1] = 1ll*dp[cur][1] * dp[child][0] % MOD;
    dp[cur][0] = 1ll*dp[cur][0] * dp[child][1] % MOD;
}

void dfs(int u, int p = -1) {
    dp[u][1] = dp[u][0] = 1;
    for(int v : adj[u]) if (v != p) {
        dfs(v, u);
        merge(u, v);
    }
}

int main() {
    memset(dp, 0, sizeof dp);
    dfs(1);
    cout << (dp[1][1] + dp[1][0]) % MOD;
}

## Flowers
Gọi $dp[i]$ là tổng độ đẹp lớn nhất của các bông hoa được chọn để bông hoa thứ $i$ là bông hoa cuối cùng.
Công thức gốc
$dp[i] = \max(dp[j] + a[i])$ với $1 \le j < i, h[j] < h[i]$

Cách làm kinh điển: số trạng thái O(n) * chi phí chuyển O(n) => O(n^2)

Tối ưu chi phí chuyển: tìm $j$ sao cho $dp[j]$ lớn nhất và $h[j] < h[i], j < i$.

Dùng một cây Fenwick/BIT để tối ưu độ phức tạp.
Với mỗi $i$, ta gọi truy vấn để tìm max các $dp[j]$ có $h[j] < h[i]$. Sau đó, ta cập nhật $dp[i]$ vào vị trí $h[i]$ trên cây. Độ phức tạp cho mỗi thao tác là $O(\log n)$.

Bài viết về cây Fenwick: https://cp-algorithms.com/data_structures/fenwick.html