Múa nón (Đề tự luyện HSG Tin quốc gia – Bài 3)
Đề bài
Múa nón. Có $K$ bạn đứng thành hàng, mỗi bạn cầm một chiếc nón lá (một mặt vẽ hoa sen, một mặt trơn); lúc mở màn mọi bạn quay mặt trơn ra ngoài. Có $N$ nhịp lật, nhịp $i$ cho bởi số $a_i$ $(0 \le a_i < 2^K)$: bạn thứ $j$ lật nón nếu bit thứ $j-1$ của $a_i$ bằng 1. Hình xếp $t$ $(0 \le t < 2^K)$: bạn $j$ quay mặt hoa ra ngoài khi và chỉ khi bit $j-1$ của $t$ bằng 1.
Mỗi câu hỏi $(l, r, t)$: chỉ dùng các nhịp từ $l$ đến $r$, mỗi nhịp nhiều nhất một lần (được phép không dùng nhịp nào), thực hiện từ lúc mở màn. Có bao nhiêu tập nhịp cho ra đúng hình $t$? In theo modulo $10^9 + 7$.
Dữ liệu vào: dòng 1 gồm $N, K, Q$ $(1 \le N, Q \le 10^5;\ 1 \le K \le 30)$; dòng 2 gồm $a_1..a_N$; $Q$ dòng sau mỗi dòng gồm $l, r, t$ $(1 \le l \le r \le N)$.
Kết quả: $Q$ dòng, mỗi dòng là đáp án của câu hỏi tương ứng (mod $10^9+7$).
- Subtask 1 (15%): $N, Q \le 15$.
- Subtask 2 (25%): $N, Q \le 1000$.
- Subtask 3 (25%): $l = 1$ ở mọi câu hỏi.
- Subtask 4 (35%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.
6 3 4
3 1 4 5 4 5
1 3 4
2 5 5
2 6 4
2 6 01
4
8
8Nhị phân (bit phải nhất là bạn 1): $a = 011, 001, 100, 101, 100, 101$. Câu $(1,3,4)$: chỉ có $\{3\}$. Câu $(2,5,5)$: $\{2,3\}, \{4\}, \{2,5\}, \{3,4,5\}$. Câu $(2,6,4)$: 8 cách, ví dụ $\{3\}, \{5\}, \{2,4\}, \ldots$ Câu $(2,6,0)$: 8 cách, kể cả cách không dùng nhịp nào.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Múa nónLời mở đầu
Bài này khoác áo "múa nón" nhưng thực chất là một bài đại số tuyến tính trên các bit — một mảng kiến thức rất hay xuất hiện ở đề chọn đội tuyển nhưng ít bạn được học bài bản. Mình sẽ đi từ vét cạn, qua khử Gauss, tới mẹo "giữ vị trí mới nhất" giúp trả lời $10^5$ câu hỏi trên các đoạn bất kỳ.
Nhận xét 1: lật nón chính là phép XOR
Mỗi bạn chỉ có hai trạng thái, lật hai lần thì về như cũ. Nếu ta ghi trạng thái cả hàng thành một số $K$ bit (bit $j-1$ = 1 nếu bạn $j$ đang quay mặt hoa) thì thực hiện nhịp $i$ chính là XOR trạng thái với $a_i$. Vì XOR có tính giao hoán, kết hợp, nên thứ tự thực hiện không quan trọng: dùng tập nhịp $S$ thì hình cuối cùng là $$a_{i_1} \oplus a_{i_2} \oplus \cdots \oplus a_{i_m}\quad (S = \{i_1, \ldots, i_m\}),$$ với tập rỗng cho hình $0$. Vậy câu hỏi là: đếm số tập con của $a_l, \ldots, a_r$ có XOR bằng $t$.
Hình 1. Thực hiện các nhịp đã chọn = XOR các số $a_i$ tương ứng. Thứ tự không quan trọng.
Nhận xét 2: đáp án chỉ có thể là 0 hoặc một lũy thừa của 2
Nhìn ví dụ: các đáp án là $1, 4, 8, 8$. Đây không phải trùng hợp! Phần chứng minh nằm ở Cách 2, và nó là chìa khóa của cả bài.
Cách 1Duyệt mọi tập con – O(Q·2^N·N) · 15%
Với mỗi câu hỏi, đoạn $[l, r]$ có tối đa 15 nhịp nên chỉ có $2^{15} = 32768$ tập con. Duyệt bitmask $m$ từ $0$ tới $2^{len}-1$, tính XOR các nhịp có bit bật trong $m$ và so với $t$. Bản Python làm gọn hơn: giữ danh sách XOR của mọi tập con, mỗi lần thêm một nhịp $v$ thì danh sách nhân đôi (thêm các phần tử cũ XOR $v$).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K, q;
scanf("%d %d %d", &n, &K, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (q--) {
int l, r, t;
scanf("%d %d %d", &l, &r, &t);
int len = r - l + 1;
long long cnt = 0;
for (int m = 0; m < (1 << len); m++) { // moi tap con cac nhip l..r
int x = 0;
for (int j = 0; j < len; j++)
if (m >> j & 1) x ^= a[l + j];
if (x == t) cnt++;
}
printf("%lld\n", cnt);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
p = 3 + n; out = []
for _ in range(q):
l = int(data[p]); r = int(data[p + 1]); t = int(data[p + 2]); p += 3
xs = [0] # XOR cua moi tap con cac nhip l..i
for i in range(l, r + 1):
v = a[i]
xs += [x ^ v for x in xs]
out.append(xs.count(t))
print("\n".join(map(str, out)))
main()Cách 2Cơ sở tuyến tính, khử Gauss cho từng câu hỏi – O(Q·N·K) · 40%
Cơ sở tuyến tính XOR là gì?
Coi mỗi số $K$ bit là một vec-tơ có $K$ tọa độ 0/1, phép cộng là XOR. Tập mọi giá trị XOR của các tập con của $a_l..a_r$ gọi là không gian sinh $V$. Một cơ sở của $V$ là một tập nhỏ nhất các vec-tơ mà XOR các tập con của nó tạo ra đúng $V$; số phần tử của cơ sở gọi là hạng $rk$, và $|V| = 2^{rk}$.
Cách xây cơ sở quen thuộc (khử Gauss trên bit): giữ mảng bv[b] = vec-tơ có bit cao nhất là $b$ (hoặc 0 nếu chưa có). Chèn số $x$: xét các bit từ cao xuống thấp, gặp bit $b$ đang bật trong $x$:
- nếu
bv[b] = 0: đặtbv[b] = x, hạng tăng 1, dừng; - ngược lại:
x ^= bv[b](xóa bit $b$) và đi tiếp xuống bit thấp hơn.
Nếu $x$ bị xóa hết về 0 thì $x$ đã nằm trong không gian sinh bởi các số trước đó — nhịp này "thừa". Kiểm tra $t \in V$ cũng y như vậy: khử $t$ bằng các bv[b] từ cao xuống, nếu về 0 thì tạo được.
Định lý đếm: đáp án = $2^{len - rk}$ hoặc 0
Gọi $len = r - l + 1$. Nếu $t \notin V$ thì đáp án là 0. Nếu $t \in V$:
- Gọi $Z$ là số tập con có XOR bằng $0$. Lấy một tập $S_0$ bất kỳ có XOR bằng $t$. Phép "đối xứng hiệu" $S \mapsto S \,\triangle\, S_0$ (nhịp nào có trong đúng một trong hai tập thì giữ) biến tập có XOR $= t$ thành tập có XOR $= 0$ và ngược lại, nên số tập cho $t$ bằng đúng $Z$, với mọi $t \in V$.
- Có $2^{len}$ tập con, chia đều cho $|V| = 2^{rk}$ giá trị, nên mỗi giá trị có đúng $2^{len}/2^{rk} = 2^{len - rk}$ tập con.
Kiểm tra với câu $(2, 5, 5)$: các nhịp $001, 100, 101, 100$ có hạng $2$ (cơ sở $\{100, 001\}$), $len = 4$, và $5 = 101 = 100 \oplus 001$ tạo được, nên đáp án là $2^{4-2} = 4$. Đúng như đề!
Em thử mô phỏng: chèn lần lượt các nhịp vào cơ sở rồi khử $t$.
Code: mỗi câu hỏi xây lại cơ sở của đoạn $[l, r]$ trong $O(len \cdot K)$. Lũy thừa $2^x \bmod (10^9+7)$ tính sẵn bằng mảng p2 — số mũ có thể lên tới $10^5$, đừng dùng 1LL << x!
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, K, q;
scanf("%d %d %d", &n, &K, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<long long> p2(n + 1, 1);
for (int i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % MOD;
while (q--) {
int l, r, t;
scanf("%d %d %d", &l, &r, &t);
int bv[30] = {0}, rk = 0;
for (int i = l; i <= r; i++) { // khu Gauss: chen tung nhip vao co so
int x = a[i];
for (int b = 29; b >= 0 && x; b--) {
if (!(x >> b & 1)) continue;
if (!bv[b]) { bv[b] = x; rk++; break; }
x ^= bv[b];
}
}
for (int b = 29; b >= 0; b--)
if ((t >> b & 1) && bv[b]) t ^= bv[b];
printf("%lld\n", t ? 0 : p2[r - l + 1 - rk]);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
MOD = 10**9 + 7
p2 = [1] * (n + 1)
for i in range(1, n + 1):
p2[i] = p2[i - 1] * 2 % MOD
p = 3 + n; out = []
for _ in range(q):
l = int(data[p]); r = int(data[p + 1]); t = int(data[p + 2]); p += 3
bv = [0] * 30; rk = 0
for i in range(l, r + 1): # khu Gauss: chen tung nhip vao co so
x = a[i]
while x:
b = x.bit_length() - 1
if bv[b] == 0:
bv[b] = x; rk += 1; break
x ^= bv[b]
while t:
b = t.bit_length() - 1
if bv[b] == 0: break
t ^= bv[b]
out.append(0 if t else p2[r - l + 1 - rk])
print("\n".join(map(str, out)))
main()Cách 3l = 1: một cơ sở tiền tố duy nhất – O((N + Q)·K + Q log Q) · 65%
Khi mọi câu hỏi có $l = 1$, đoạn chỉ "mọc dài ra" theo $r$. Ta sắp các câu hỏi theo $r$ tăng dần và chỉ dùng một cơ sở: chèn dần $a_1, a_2, \ldots$; tới câu hỏi có $r$ thì cơ sở hiện tại chính là cơ sở của $a_1..a_r$, hạng $rk$ là số vec-tơ đã đặt được. Mỗi nhịp chèn một lần, mỗi câu hỏi khử $t$ một lần: $O(K)$ mỗi việc.
Code dưới đây kiểm tra nếu có câu hỏi $l \ne 1$ thì quay về Cách 2, nên Cách 3 ăn được subtask 1, 2, 3.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, K, q;
vector<int> a, ql, qr, qt;
vector<long long> p2;
void cach2() { // nhu Cach 2: dung lai co so cho tung cau hoi
for (int k = 0; k < q; k++) {
int bv[30] = {0}, rk = 0, t = qt[k];
for (int i = ql[k]; i <= qr[k]; i++) {
int x = a[i];
for (int b = 29; b >= 0 && x; b--) {
if (!(x >> b & 1)) continue;
if (!bv[b]) { bv[b] = x; rk++; break; }
x ^= bv[b];
}
}
for (int b = 29; b >= 0; b--) if ((t >> b & 1) && bv[b]) t ^= bv[b];
printf("%lld\n", t ? 0 : p2[qr[k] - ql[k] + 1 - rk]);
}
}
int main() {
scanf("%d %d %d", &n, &K, &q);
a.assign(n + 1, 0); ql.resize(q); qr.resize(q); qt.resize(q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
bool allL1 = true;
for (int k = 0; k < q; k++) { scanf("%d %d %d", &ql[k], &qr[k], &qt[k]); if (ql[k] != 1) allL1 = false; }
p2.assign(n + 1, 1);
for (int i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % MOD;
if (!allL1) { cach2(); return 0; }
vector<int> ord(q); // l = 1: xu ly cau hoi theo r tang dan
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [](int x, int y) { return qr[x] < qr[y]; });
vector<long long> ans(q);
int bv[30] = {0}, rk = 0, r = 0;
for (int k : ord) {
while (r < qr[k]) { // them nhip r+1 vao co so cua tien to
int x = a[++r];
for (int b = 29; b >= 0 && x; b--) {
if (!(x >> b & 1)) continue;
if (!bv[b]) { bv[b] = x; rk++; break; }
x ^= bv[b];
}
}
int t = qt[k];
for (int b = 29; b >= 0; b--) if ((t >> b & 1) && bv[b]) t ^= bv[b];
ans[k] = t ? 0 : p2[r - rk];
}
for (int k = 0; k < q; k++) printf("%lld\n", ans[k]);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
MOD = 10**9 + 7
p2 = [1] * (n + 1)
for i in range(1, n + 1):
p2[i] = p2[i - 1] * 2 % MOD
ql = [int(x) for x in data[3 + n::3]]
qr = [int(x) for x in data[4 + n::3]]
qt = [int(x) for x in data[5 + n::3]]
ans = [0] * q
if any(l != 1 for l in ql): # nhu Cach 2
for k in range(q):
bv = [0] * 30; rk = 0; t = qt[k]
for i in range(ql[k], qr[k] + 1):
x = a[i]
while x:
b = x.bit_length() - 1
if bv[b] == 0:
bv[b] = x; rk += 1; break
x ^= bv[b]
while t:
b = t.bit_length() - 1
if bv[b] == 0: break
t ^= bv[b]
ans[k] = 0 if t else p2[qr[k] - ql[k] + 1 - rk]
else: # l = 1: xu ly theo r tang dan
bv = [0] * 30; rk = 0; r = 0
for k in sorted(range(q), key=qr.__getitem__):
while r < qr[k]:
r += 1; x = a[r]
while x:
b = x.bit_length() - 1
if bv[b] == 0:
bv[b] = x; rk += 1; break
x ^= bv[b]
t = qt[k]
while t:
b = t.bit_length() - 1
if bv[b] == 0: break
t ^= bv[b]
ans[k] = 0 if t else p2[r - rk]
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()Cách 4Cơ sở tiền tố "giữ vị trí mới nhất" – O((N + Q)·K) · 100%
Ta vẫn muốn một cơ sở chạy theo $r$, nhưng phải trả lời được với mọi $l$. Ý tưởng: trong lúc chèn, ngoài vec-tơ bv[b] ta lưu thêm bp[b] = vị trí "đại diện" của nó, và luôn ưu tiên giữ vec-tơ có vị trí lớn hơn (mới hơn).
Chèn $x = a_r$ với vị trí $p = r$, đi từ bit cao xuống, gặp bit $b$ bật trong $x$:
- nếu
bv[b] = 0: đặtbv[b] = x, bp[b] = p, dừng; - nếu
bp[b] < p: đổi chỗ $(bv[b], bp[b]) \leftrightarrow (x, p)$ — vec-tơ mới hơn được giữ lại ở hàng $b$, vec-tơ cũ hơn bị đẩy xuống tiếp tục đi; - rồi
x ^= bv[b]như thường.
bv[b] có bp[b] ≥ l tạo thành một cơ sở của không gian sinh bởi $a_l..a_r$. Vậy câu hỏi $(l, r, t)$: $rk$ = số hàng có bp[b] ≥ l, và khử $t$ chỉ bằng các hàng đó.Vì sao đúng? (ý chính) Mỗi hàng bv[b] luôn là XOR của một số $a_i$ có chỉ số $\ge$ bp[b] (khi XOR hai vec-tơ, vec-tơ đi tiếp mang vị trí nhỏ hơn trong hai vị trí, nên bất biến này được giữ). Do đó các hàng có bp[b] ≥ l nằm trong không gian của $a_l..a_r$. Ngược lại, để thấy chúng đủ sinh ra cả không gian: hãy tưởng tượng chèn các nhịp theo thứ tự ngược $a_r, a_{r-1}, \ldots, a_l$ vào cơ sở Gauss thường — số vec-tơ độc lập ta nhận được chính là $rk(l, r)$. Quy tắc "giữ vị trí lớn hơn" làm cho cơ sở tiền tố mô phỏng đúng quá trình đó: một nhịp $a_i$ chỉ bị loại (về 0) khi nó phụ thuộc vào các nhịp mới hơn nó. Vì vậy với mỗi $l$, số hàng có bp ≥ l bằng đúng số nhịp trong $[l, r]$ không phụ thuộc vào các nhịp mới hơn, tức là bằng $rk(l, r)$.
Bây giờ chỉ cần gom câu hỏi theo $r$ (danh sách liên kết head/nxt), quét $r$ từ 1 tới $N$, chèn $a_r$ rồi trả lời các câu hỏi có đúng $r$ đó. Thử mô phỏng: hàng nào có bp ≥ l được tô xanh — đó là cơ sở của đoạn $[l, r]$.
Code đầy đủ:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, K, q;
scanf("%d %d %d", &n, &K, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<int> ql(q), qt(q), head(n + 1, -1), nxt(q);
for (int k = 0; k < q; k++) {
int r;
scanf("%d %d %d", &ql[k], &r, &qt[k]);
nxt[k] = head[r]; head[r] = k; // gom cau hoi theo r
}
vector<long long> p2(n + 1, 1);
for (int i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % MOD;
int bv[30] = {0}, bp[30] = {0}; // co so: vec-to bv[b] co bit cao nhat b, vi tri bp[b]
vector<long long> ans(q);
for (int r = 1; r <= n; r++) {
int x = a[r], p = r;
for (int b = 29; b >= 0 && x; b--) {
if (!(x >> b & 1)) continue;
if (!bv[b]) { bv[b] = x; bp[b] = p; break; }
if (bp[b] < p) { swap(bv[b], x); swap(bp[b], p); } // giu vec-to moi hon (vi tri lon hon)
x ^= bv[b];
}
for (int k = head[r]; k != -1; k = nxt[k]) {
int l = ql[k], t = qt[k], rk = 0;
for (int b = 0; b < 30; b++) if (bp[b] >= l) rk++; // bp = 0 neu chua co
for (int b = 29; b >= 0 && t; b--)
if ((t >> b & 1) && bp[b] >= l) t ^= bv[b];
ans[k] = t ? 0 : p2[r - l + 1 - rk];
}
}
string out;
for (int k = 0; k < q; k++) { out += to_string(ans[k]); out += '\n'; }
fputs(out.c_str(), stdout);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[2])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[2 + i])
ql = [0] * q; qt = [0] * q; nxt = [0] * q; head = [-1] * (n + 1)
p = 3 + n
for k in range(q):
ql[k] = int(data[p]); r = int(data[p + 1]); qt[k] = int(data[p + 2]); p += 3
nxt[k] = head[r]; head[r] = k # gom cau hoi theo r
MOD = 10**9 + 7
p2 = [1] * (n + 1)
for i in range(1, n + 1):
p2[i] = p2[i - 1] * 2 % MOD
bv = [0] * 30; bp = [0] * 30 # co so: bv[b] co bit cao nhat b, vi tri bp[b]
ans = [0] * q
for r in range(1, n + 1):
x = a[r]; pos = r
while x:
b = x.bit_length() - 1
v = bv[b]
if v == 0:
bv[b] = x; bp[b] = pos; break
if bp[b] < pos: # giu vec-to moi hon (vi tri lon hon)
bv[b] = x; x = v; v = bv[b]
bp[b], pos = pos, bp[b]
x ^= v
k = head[r]
while k >= 0:
l = ql[k]; t = qt[k]; rk = 0
for pp in bp:
if pp >= l: rk += 1
while t:
b = t.bit_length() - 1
if bp[b] >= l:
t ^= bv[b]
else:
break
ans[k] = 0 if t else p2[r - l + 1 - rk]
k = nxt[k]
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()- Quên đổi chỗ (giữ vec-tơ cũ ở mỗi hàng rồi lọc
bp ≥ l): vẫn đúng khi $l = 1$ nhưng sai với đoạn bất kỳ. - Quên kiểm tra $t$ có tạo được không: khi $t$ nằm ngoài không gian sinh, đáp án là 0.
- Lũy thừa 2 bằng dịch bit: $len - rk$ có thể tới $10^5$, phải dùng mảng lũy thừa theo modulo.
- Tập rỗng là một cách hợp lệ khi $t = 0$ — công thức $2^{len - rk}$ đã tự tính nó.
Chạy tay từng dòng code C++ ở trên (để dễ theo dõi: $N \le 10$, $Q \le 6$, $a_i, t < 64$):
Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: subtask 1 có 8 test (gồm ví dụ, $N = 1$, $K = 1$, toàn số 0), subtask 2 có 8 test ($N = Q = 1000$), subtask 3 có 6 test và subtask 4 có 8 test ($N = Q = 10^5$). Dãy nhịp được sinh theo nhiều kiểu: ngẫu nhiên 30 bit, chia khối mỗi khối lấy từ một không gian con riêng (hạng của đoạn thay đổi liên tục), "nhịp mới" xuất hiện thưa thớt giữa rất nhiều nhịp phụ thuộc, nhịp chỉ 1–2 bit, rất nhiều nhịp bằng 0. Hình $t$ được chọn cả trong lẫn ngoài không gian sinh (kể cả dùng một nhịp nằm ngay sát ngoài đoạn).
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – duyệt mọi tập con | 8/8 | TLE | TLE | TLE | 15 |
| Cách 2 – khử Gauss cho từng câu hỏi | 8/8 | 8/8 | TLE | TLE | 40 |
| Cách 3 – l = 1: cơ sở tiền tố | 8/8 | 8/8 | 6/6 | TLE | 65 |
| Cách 4 – giữ vị trí mới nhất (lời giải đầy đủ) | 8/8 | 8/8 | 6/6 | 8/8 | 100 |
| Sai: quên đổi chỗ (giữ vec-tơ cũ) | 5/8 | 0/8 | 6/6 | 0/8 | 34,38 |
| Sai: dùng cơ sở tiền tố cho mọi đoạn | 4/8 | 0/8 | 6/6 | 0/8 | 32,5 |
Sai: lũy thừa 2 bằng 1LL << x | 8/8 | 0/8 | 0/6 | 0/8 | 15 |
| Sai: quên kiểm tra t có tạo được không | 2/8 | 1/8 | 0/6 | 0/8 | 6,88 |
Để ý: ví dụ trong đề được chọn sao cho lời giải "quên đổi chỗ", "quên kiểm tra t" và "dịch bit" đều in đúng 1 4 8 8 — mọi câu hỏi trong ví dụ đều tạo được hình, số mũ nhỏ, và trên đúng bốn câu hỏi đó cơ sở "giữ vec-tơ cũ" tình cờ vẫn đúng (trong khi câu $(4, 6, 1)$ trên cùng dãy nó sẽ in 0 thay vì 2). Qua ví dụ chưa nói lên điều gì!
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: lời giải chuẩn chạy tối đa 0,09 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3 giây. Lời giải chuẩn được đối chiếu với chương trình vét cạn (thử mọi tập con) trên 1900 test nhỏ ngẫu nhiên, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và chạy tối đa khoảng 2,5 giây ngay cả trên CPython.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét