DeMen Blog #8: Lời giải bài K - ICPC miền Nam 2026
Tác giả: Võ Khắc Triệu (DeMen100ns)
Hello ae, cũng được một thời gian rồi nhỉ. Dạo này học hành nhiều cũng hơi chán nên cũng muốn ngồi viết blog algo cho ae đọc xíu. Kỳ thi miền Nam vừa mới trôi quá với quả bộ đề khó kinh khủng, nên mình cũng muốn showcase ae lời giải của bài khó nhất đề (chắc thế?).
Đề bài (Locker Riddle 2)
Cho xâu nhị phân độ dài . Mỗi bước, có xác suất là các bit là bội của sẽ được flip (, chỉ có một được chọn).
Tính expected số bước để xâu nhị phân lần đầu tiên full .
Kiến thức cần biết
- Hàm sinh (Generating Function)
Lời giải
Biến đổi bài toán
Nếu các bạn đã đọc bài Locker Riddle 1 trong cùng đề, bạn sẽ nhận ra, sequence of operation (unordered) cần làm, nếu tối ưu độ dài, là duy nhất và độc lập. Tồn tại song ánh giữa xâu và min-length sequence of operation (unordered).
Từ đó, ta có thể biến đổi lại bài toán như sau:
Cho xâu nhị phân độ dài , Mỗi bước, có xác suất bit thứ sẽ được flip (, chỉ có một được chọn).
Tính expected số bước để xâu nhị phân lần đầu tiên full .
Với các bit bật của hiện tại thuộc min-length sequence of operation để biến thành full .
Ví dụ: , do ta có thể thực hiện operation flip bội của 1 và bội của 2 để tắt hết các bit trên xâu nhị phân .
Generating Fun (tạo niềm vui)
Để dễ làm việc, ta sẽ gọi .
Gọi là xác suất để xâu là full lần đầu tiên sau đúng bước. Vậy đáp án sẽ là . Nhưng mà đáng tiếc không trivial để tính như vậy.
Giờ làm bài toán dễ hơn một chút nha. Gọi là xác suất để một xâu full vẫn là full sau đúng bước (không nhất thiết phải là lần đầu). Nếu đã học về hàm sinh, ta có thể dựng hàm sinh của là EGF :
Tiếp theo, nâng cấp một chút, gọi là xác suất để xâu trở thành xâu full sau đúng bước (không nhất thiết phải là lần đầu). Thay đổi chỉ diễn ra nếu có bit của bật thì thay vì flip chẵn lần thì sẽ là lẻ lần, vì:
Từ đó, ta có hàm sinh của là EGF :
Với là nếu bit của bật, là nếu bit đang tắt.
Nhưng còn thì sao?
Thật ra nếu bạn để ý, sự kiện mà biểu diễn sẽ xảy ra như sau:
- Trong bước đầu, xâu B sẽ trở thành xâu lần đầu tiên
- Trong bước sau, xâu sẽ quay trở lại xâu .
Như vậy, . Trông quen không? Nó chính là tích chập (convolution) trong OGF đấy!
Gọi là OGF của , ta có:
Quay lại với đáp án, ta biết đáp án cần tìm là , nếu biến đổi lại, nó sẽ là !! Vì ta biết , ta có:
Ok hay đấy, nma mình mới có với thôi mà?
EGF -> OGF
Từ EGF sang OGF, thật ra chỉ cần nhân trên hệ số của là được. Giờ ta thử làm với . Để như vậy hơi khó mà lấy hệ số nên ta cần biến đổi lại một chút.
Ta có:
Nếu để ý, ta có thể biểu diễn dưới dạng:
Với hệ số có thể được tính bằng DP (tự nghĩ công thức DP nhé ^^).
Ta có:
Khi chuyển sang OGF (nhân vào hệ số của ), trở thành:
Vậy:
Tương tự, chính là với (mọi ), nên cũng biểu diễn được dưới dạng và
Edge case
Vấn đề còn lại là, khi consider tổng của và tại và thì sẽ xảy ra trường hợp chia cho , nên ta phải khử đi bằng cách nhân cả hai cho . Đặt:
Vậy giờ:
Ta có:
Vậy ta chỉ cần tính và thế số vào là có thể tính được trong .
Conclusion:
Độ phức tạp là , chủ yếu do phải DP đoạn tính .
Bài này còn một lời giải thuần xác suất nữa, cũng tương đối khó nghĩ (bài tập cho người đọc <("))
Implementation
/*Author : DeMen100ns (Vo Khac Trieu)School: National University of SingaporeAim:- International Grandmaster Codeforces (2600)*/
#include <bits/stdc++.h>
using namespace std;
const long long INF = numeric_limits<long long>::max() / 2;const int INF_int = 1e9 + 7;
const int mod = 998244353;
struct mint { int a;
mint() : a(0) {} mint(long long x) : a(int(x % mod)) { if (a < 0) a += mod; } static mint raw(int x) { mint r; r.a = x; return r; } mint I() const { return raw(1); } mint operator-() const { return raw(a ? mod - a : 0); }
friend mint operator+(mint x, mint y) { int s = x.a + y.a; return raw(s >= mod ? s - mod : s); } friend mint operator-(mint x, mint y) { int s = x.a - y.a; return raw(s < 0 ? s + mod : s); } friend mint operator*(mint x, mint y) { return raw(int(1ll * x.a * y.a % mod)); } friend mint operator/(mint x, mint y) { return x * y.bpow(mod - 2); }
mint &operator+=(mint t) { return *this = *this + t; } mint &operator-=(mint t) { return *this = *this - t; } mint &operator*=(mint t) { return *this = *this * t; } mint &operator/=(mint t) { return *this = *this / t; }
friend bool operator==(mint x, mint y) { return x.a == y.a; } friend bool operator!=(mint x, mint y) { return x.a != y.a; }
explicit operator int() const { return a; }
mint bpow(long long n) const { mint r = raw(1), p = *this; for (; n; n >>= 1, p = p * p) if (n & 1) r = r * p; return r; } mint inv() const { return bpow(mod - 2); }};
vector<mint> coefficients(const vector<int>& p, const vector<int>& B, int S) { const mint inv2 = mint::raw((mod + 1) / 2);
vector<mint> dp(2 * S + 1); dp[S] = 1; int sum = 0;
for (int i = 0; i < (int)p.size(); ++i) { vector<mint> next(2 * S + 1);
for (int j = -sum; j <= sum; ++j) { mint value = dp[j + S] * inv2;
next[j + p[i] + S] += value; next[j - p[i] + S] += B[i] ? -value : value; }
sum += p[i]; dp.swap(next); }
return dp;}
vector <int> transform(vector <int> A, int n){ for (int i = 1; i <= n; ++i) { if (A[i - 1]) { for (int j = 2 * i; j <= n; j += i) { A[j - 1] ^= 1; } } }
return A;}
mint ans(const vector <mint> &a, const vector <mint> &b, int S){ //Note that a_i = a[i - S]
mint G1 = a[2 * S]; // G(1) = a_S mint H1 = b[2 * S]; // H(1) = b_S
mint dG = 0, dH = 0; //G'(1) and H'(1)
for (int j = -S; j < S; ++j) { mint factor = mint(S) / (S - j);
dG -= a[j + S] * factor; dH -= b[j + S] * factor; }
mint answer = (dG * H1 - dH * G1) / (H1 * H1); return answer;}
void solve() { int n, S; cin >> n >> S;
vector<int> A(n), p(n), B; for (int& x : A) cin >> x; for (int& x : p) cin >> x;
B = transform(A, n);
vector<mint> a = coefficients(p, B, S); vector<mint> b = coefficients(p, vector<int>(n, 0), S);
cout << (int)ans(a, b, S) << '\n';}
signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1; cin >> t; for(int test = 1; test <= t; ++test){ solve(); }}
