###### tags: `TanKhoa`
# Buổi 5+6 (5+11/4/2022)

## Chẵn lẻ (B1 THT STR A)
Tích $a\times b \times c$ lẻ $\Rightarrow$ $a, b, c$ cùng lẻ.

$\Rightarrow$ cứ đặt c = 1, kiểm tra $a, b$ có lẻ hay không.

$a, b$ đều lẻ thì in ra `Y`, còn không thì in ra `N`.

## Chọn cặp (B2 THT STR A)
Việc chọn một số trong các số chẵn độc lập với việc chọn một số trong các số lẻ, nên số cách bắt cặp giữa một số chẵn và một số lẻ bằng số khả năng chọn số chẵn nhân với số khả năng chọn số lẻ.

Từ $1 \rightarrow k$ có `k / 2` số chẵn $\Rightarrow$ số lượng số lẻ là `k - k / 2`

Đáp án của chúng ta là `(k/2) * (k-k/2)`

## Bộ ba số (B3 THT STR A)
Đồng dư: $a \equiv b (\text{mod} \ c) \Rightarrow a\ \text{mod} \ c = b\ \text{mod} \ c$
$\Rightarrow a \equiv 0 (\text{mod} \ b) \Leftrightarrow$ $a$ chia hết cho $b$.

$a+b \equiv 0 (\text{mod} \ k)$, $b+c \equiv 0 (\text{mod} \ k)$, $c+a \equiv 0 (\text{mod} \ k)$
$\Rightarrow a+b \equiv b+c \equiv c+a \equiv 0 (\text{mod} \ k)$
$a+b \equiv b+c (\text{mod} \ k) \Rightarrow a \equiv c (\text{mod} \ k)$. Làm tương tự, ta suy ra $a \equiv b \equiv c (\text{mod} \ k)$ **(1)**

Như vậy, khi chia lấy dư cho $k$, các phép toán $a+b, b+c, c+a$ đều không khác gì các phép toán $2a, 2b, 2c$, tức là chúng đều có ý nghĩa như nhau khi chia lấy dư cho $k$ (xét hệ modulo $k$)

Khi chia cho $k$ có thể ra các số dư từ $0$ tới $k-1$.
Trong số đó, chỉ có $0$ và $\frac{k}{2}$ (nếu k chẵn) khi nhân 2 sẽ chia hết cho $k$.
$\Rightarrow a \equiv b \equiv c \equiv 0(\text{mod} \ k)$ hoặc $a \equiv b \equiv c \equiv \frac{k}{2}(\text{mod} \ k)$ nếu $k$ chẵn.

**TH1:** Đếm số cách chọn để $a, b, c$ cùng chia hết cho $k$.
Có `n/k` số chia hết cho 3 $\Rightarrow$ có `(n/k)^3` cách chọn bộ ba số $a, b, c$

**TH2 (nếu k chẵn):** Đếm số cách chọn để $a, b, c$ cùng chia $k$ dư $k/2$
Từ $1 \rightarrow n$, có bao nhiêu số chia $k$ dư $k/2$?
Các số chia cho $k$ dư $k/2$, khi cộng thêm cho $k/2$ thì sẽ chia hết cho $k$.
Như vậy ta đưa về bài toán "Từ $(k/2+)1 \rightarrow n + k/2$, có bao nhiêu số chia hết cho $k$"
Đáp án của chúng ta là `[ (n+k/2)/k ]^3`

Sau khi tính cả hai trường hợp, cộng hai đáp án vào.

## Bóng đèn (TS10 LQĐ)
Khi tác động một số lẻ lần lên bóng đèn, bóng đèn sẽ được bật, và ngược lại.

Bóng đèn thứ $9$ sẽ được các thao tác thứ $1, 3, 9$ tác động $\Rightarrow$ bóng đèn $9$ từ tắt thành bật.
Bóng đèn thứ $12$ sẽ được các thao tác thứ $1, 2, 3, 4, 6, 12$ tác động $\Rightarrow$ bóng đèn $9$ vẫn bị tắt.

Nhìn các ví dụ, ta có kết luận: Bóng đèn thứ $i$ được bật nếu nó có số ước là lẻ $\Leftrightarrow$ $i$ là số chính phương.

Số lượng số chính phương từ $1 \rightarrow x$ bất kỳ là $\lfloor \sqrt{x} \rfloor$
Đáp án của chúng ta là $\lfloor \sqrt{r} \rfloor - \lfloor \sqrt{l-1} \rfloor$

**Lưu ý:** Khi gặp các bài có dạng "đếm số lượng số thỏa mãn tính chất trong đoạn từ $l$ tới $r$", (trong đa số trường hợp,) ta tìm công thức đếm số thỏa mãn điều kiện từ $1 \rightarrow x$ bất kỳ (tạm viết là $f(x)$). Đáp án sẽ là $f(r) - f(l-1)$.

## Tạo nhiệm vụ cùng Imposter
Đặt $\Sigma=A[1] + A[2] + \dots + A[n]$.
Số việc người thứ $i$ phải làm là $\Sigma - A[i]$.

## pyramid1
Giả sử các tam giác cuối đều có đáy (tức là thêm n lá bài vào cuối).

Ta thấy là tháp độ cao $n$ thì có $n(n+1) / 2$ hình tam giác.
$\Rightarrow$ cần dùng $3n(n+1)/2$ lá bài

Giờ ta lấy lại $n$ lá bài.
**Đáp án là: $3n(n+1)/2 - n$.**

## Đếm hình (TS10 LQĐ)
Gọi kích thước chiều ngang, chiều dọc của HCN lớn là $x, y$.
Gọi kích thước chiều ngang, chiều dọc của HCN nhỏ là $u, v$.

- **Tính công thức**
Số lượng HCN nhỏ trong HCN lớn $x\times y$ bất kỳ là $\frac{x(x+1)}{2}\times\frac{y(y+1)}{2}$
Số lượng HV nhỏ trong HCN lớn $x \times y$ là: $xy + (x-1)(y-1) + (x-2)(y-2) + \dots + (x-y+1)$
Sau khi vẽ minh họa, ta ra được công thức là: $\frac{y(y+1)(2y+1)}{6} + (x-y)\frac{y(y+1)}{2}$.

- **Phân chia**

**Lưu ý:**

Tính số HCN thì mod đáp án cho $10^9+7$, NHƯNG tính số HV thì **mod đáp án cho $10^9+6$**.

## Xích lại gần nhau

### Cày trâu

int ans = 0;
for (int beg = 1; beg <= n; beg++){
    int sum = 0;
    for (int end = beg; end <= n; end++){
        sum += a[end]; if (sum > t) break;
        
        int len = end - beg + 1;
        if (len > ans) ans = len;
    }
}

cout << ans;

### Thuật chuẩn
Sử dụng thuật toán hai con trỏ

int ans = 0;
int sum = 0, end = 0;
for (int beg = 1; beg <= n; beg++){
    while (end + 1 <= n and sum + a[end + 1] <= t){
        sum += a[end + 1]; end++;
        
        int len = end - beg + 1;
        if (len > ans) ans = len;
    }
    sum -= a[beg];
}

Thuật toán tìm kiếm nhị phân

// xây dựng mảng cộng dồn:
ll s[10^5];
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

// code
int ans = 0;
for (int beg = 1; beg <= n; beg++){
    int l = beg, r = n;
    while (l <= r){
        int mid = (l + r) / 2;
        if (s[mid] - s[beg - 1] <= t)
            ans = max(ans, mid - beg + 1),
            mid = l + 1;
        else
            mid = r - 1;
    }
}

cout << ans;

## Mũ của 2

### Cày trâu

ll ans = 0;
for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
        ans += __builtin_popcount(a[i] + a[j]) == 1;
cout << ans;

### Thuật chuẩn
- **Nhận xét 1:** Số lượng số có dạng $2^k$ mà nhỏ hơn $10^9$ chỉ tầm khoảng 30.
- **Nhận xét 2:** Khi đã có $2^k$ và $a[i]$ thì số còn lại cần tìm là $2^k - a[i]$

Để đếm xem trong mảng $a$ có bao nhiêu số $x$:
- Sắp xếp mảng lại
- Chặt nhị phân để tìm vị trí bắt đầu, kết thúc của đoạn chứa số $x$ liên tiếp nhau
+ Mọi số sau vị trí bắt đầu luôn $\ge x$
+ Mọi số trước vị trí kết thúc luôn $\le x$

sort(a + 1, a + 1 + n);

int cntAppear(int value){
    int beg = 0, l = 1, r = n;
    while (l <= r){                       // chặt nhị phân tìm vị trí bắt đầu
        int mid = (l + r) / 2;
        if (a[mid] >= value)              // Mọi số sau vị trí bắt đầu luôn >= x
            beg = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    if (a[beg] != value) return 0;        // nếu không tồn tại vị trí bắt đầu
    
    int end = beg, l = beg, r = n;
    while (l <= r){                       // chặt nhị phân tìm vị trí kết thúc
        int mid = (l + r) / 2;
        if (a[mid] <= value)              // Mọi số trước vị trí kết thúc luôn <= x
            end = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    
    return end - beg + 1;
}

ll ans = 0;
for (int i = 1; i <= n; i++)
    for (int k = 0; k <= 30; k++){
        int need = (1 << k) - a[i];
        int cnt = cntAppear(need);
        if (cnt > 0 and need == a[i]) cnt--;
        ans += cnt;
    }
cout << ans / 2;