Two Sets II
Đề bài
Two Sets II – Hai tập hợp II (CSES 1093)
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 512 MB.
Nhiệm vụ của bạn là đếm số cách chia các số $1, 2, \ldots, n$ thành hai tập hợp có tổng bằng nhau.
Ví dụ, nếu $n = 7$ thì có bốn cách chia:
- $\{1, 3, 4, 6\}$ và $\{2, 5, 7\}$
- $\{1, 2, 5, 6\}$ và $\{3, 4, 7\}$
- $\{1, 2, 4, 7\}$ và $\{3, 5, 6\}$
- $\{1, 6, 7\}$ và $\{2, 3, 4, 5\}$
Dữ liệu vào: Dòng duy nhất chứa một số nguyên $n$.
Kết quả: In ra đáp án sau khi chia lấy dư cho $10^9 + 7$.
Ràng buộc: $1 \le n \le 500$.
74Lời mở đầu
Bài này là một bài kinh điển trong bộ CSES: nhìn thì là bài đếm tập con có tổng cho trước (quy hoạch động quen thuộc), nhưng có thêm một "cái bẫy" ở bước cuối – phải chia đôi một số đã bị chia lấy dư. Để vượt qua nó mình sẽ dẫn các bạn qua nghịch đảo modulo, định lý Fermat nhỏ và luỹ thừa nhanh. Hy vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJTóm tắt đề bài một cách đơn giản nhất: ta cần đếm số cách chia các số $1, 2, \ldots, n$ $(1 \le n \le 500)$ thành 2 tập hợp có tổng bằng nhau, in ra kết quả chia dư cho $10^9 + 7$.
Giải thích ví dụ $n = 7$: tổng các số từ $1$ tới $7$ là $28$, nên mỗi tập phải có tổng đúng $14$. Có đúng 4 cách chia như đề liệt kê. Để ý mỗi cách chia gồm 2 tập con cùng có tổng $14$, nên tổng cộng có $8$ tập con có tổng $14$:
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Nhận xétĐưa về đếm tập con, rồi chia đôi
Đáp án = một nửa số tập con có tổng bằng nửa tổng dãy
Ở ví dụ trên, tổng của các tập hợp đều bằng $14$, bằng một nửa tổng các số từ $1$ tới $7$ (là $28$). Có $8$ tập con có tổng $14$, mà đáp án là $4$. Vì sao vậy?
- Ta cần chia dãy thành 2 tập có tổng bằng nhau, mà cả dãy có tổng $S(n)$, vậy mỗi tập phải có tổng $S(n) / 2$.
- Mỗi cách chia ứng với đúng 2 tập con có tổng $S(n)/2$ (tập này và phần bù của nó). Ngược lại, mỗi tập con có tổng $S(n)/2$ thì phần bù cũng có tổng $S(n)/2$.
Tính tổng 1 + 2 + … + n
Có thể dùng một vòng for, độ phức tạp $O(n)$ với $n \le 500$ thì cũng không sao. Nhưng ta hoàn toàn tính được trong $O(1)$ bằng công thức $S(n) = \dfrac{n(n + 1)}{2}$.
Bạn nào nhớ luôn thì càng tốt vì công thức này dùng trong rất nhiều bài. Còn nếu không nhớ, hoặc cần tính tổng dãy như $0 + 2 + 4 + \ldots + 2n$ hay $1 + 3 + 5 + \ldots + (2n - 1)$, thì chỉ cần nhớ đúng 1 công thức tổng $n$ số hạng đầu của cấp số cộng ($u_n = u_{n-1} + d$):
Công thức thứ 2 dùng khi không biết $u_n$. Với dãy $1, 2, \ldots, n$ thì $u_1 = 1$, $u_n = n$, $d = 1$ nên $S(n) = \dfrac{n(1 + n)}{2}$.
Nếu $S(n)$ là số lẻ thì không thể chia đôi được, đáp án chắc chắn là $0$. Còn nếu $S(n)$ chẵn thì ta đếm số tập con có tổng $sum = S(n)/2 = \dfrac{n(n+1)}{4}$.
Cái bẫy: chia đôi sau khi đã chia dư
Trong quá trình đếm, kết quả rất lớn (cỡ $2^{500}$) nên ta phải liên tục chia dư cho $mod = 10^9 + 7$. Theo đồng dư thức $(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$, chia dư trong lúc tính cho kết quả giống hệt tính xong mới chia dư. Phép $+$, $-$, $\times$ đều có đồng dư thức như vậy, nhưng phép chia thì không:
/ 2 là sai; mà không chia dư thì tràn số. Kẹt!Nghịch đảo modulo và định lý Fermat nhỏ
Để giải quyết đoạn này ta cần biết về nghịch đảo modulo (modular inverse). Ta không có đồng dư thức cho phép chia nhưng có cho phép nhân, vậy biến phép chia thành phép nhân:
$\dfrac{a}{b} = a \cdot \dfrac{1}{b} = a \cdot b^{-1}$ ⇒ $\left(\dfrac{a}{b}\right) \bmod m = \big((a \bmod m) \cdot (b^{-1} \bmod m)\big) \bmod m$.
Giờ chỉ cần tính $b^{-1} \bmod m$. Định lý Fermat nhỏ phát biểu: "Nếu $p$ là số nguyên tố và $a$ là số nguyên không chia hết cho $p$ thì $a^{p-1} - 1$ chia hết cho $p$", tức là $a^{p-1} \bmod p = 1$. Đề cho $mod = 10^9 + 7$ chính là một số nguyên tố. Nhân cả 2 vế với $a^{-1}$:
Bài này $b = 2$ vì ta cần chia đôi. Lưu ý không phải lúc nào $b^{-1}$ cũng tồn tại, nó chỉ tồn tại khi $\gcd(b, m) = 1$; ở đây $m$ nguyên tố nên đương nhiên $\gcd(2, m) = 1$. Vậy $2^{-1} \bmod m = 2^{m-2} \bmod m$ (tính ra là $500000004$; kiểm tra: $2 \cdot 500000004 = 1000000008 \equiv 1 \pmod{10^9+7}$ ✅).
Luỹ thừa nhanh bằng chia để trị
$m - 2 = 10^9 + 5$. Nếu tính $2^{10^9+5}$ rồi mới chia dư thì chắc chắn tràn số. Còn nếu nhân $a \cdot a \cdot a \ldots$ đủ $b$ lần bằng vòng for (vừa nhân vừa chia dư) thì độ phức tạp $O(b) = O(10^9)$, chắc chắn TLE vì 1 giây chỉ chạy được tầm $10^8$ phép tính. Ta cần luỹ thừa nhị phân hoặc chia để trị, chỉ tốn $O(\log_2 b)$. Tách $a^b$ thành 3 trường hợp:
- $b = 0$: $a^0 = 1$.
- $b$ chẵn: $a^b = a^{b/2} \cdot a^{b/2}$.
- $b$ lẻ: lúc này
b / 2trong C++ làm tròn xuống (ví dụ11 / 2 = 5), nên $a^b = a^{b/2} \cdot a^{b/2} \cdot a$.
Với $a^b \bmod m$ thì cứ áp đồng dư thức của phép nhân vào. Ta viết hàm đệ quy powMod(a, b, m) trả về $a^b \bmod m$:
- Điều kiện dừng:
b == 0thì trả về $1$. - Xử lý chạy: dù $b$ chẵn hay lẻ đều cần $a^{b/2} \bmod m$, nên gọi
half = powMod(a, b / 2, m). Rồi gán lạihalf = (half * half) % m. Nếu $b$ lẻ thì trả về(half * (a % m)) % m, còn $b$ chẵn thì trả vềhalfluôn.
typedef long long ll;
ll powMod(ll a, ll b, ll m) {
if(b == 0) {
return 1;
}
ll half = powMod(a, b / 2, m);
half = (half * half) % m;
if(b % 2) {
return (half * (a % m)) % m;
}
return half;
}Ví dụ nhỏ: $3^{11}$ đi qua chuỗi lời gọi $b = 11 \to 5 \to 2 \to 1 \to 0$, chỉ 5 lời gọi thay vì 11 phép nhân:
Với $b = 10^9 + 5$ thì chỉ cần khoảng $30$ lời gọi. Các bạn sẽ thấy rõ trong khung chạy tay ở dưới (phần cuối chương trình).
Cách 1Quy hoạch động bảng 2 chiều – O(n · n(n+1)/4)
Giờ chỉ còn vấn đề đếm số tập con có tổng bằng $sum$. Vì các phần tử của dãy là $1, 2, \ldots, n$ nên ở đây $a[i] = i$ luôn. Ta có 4 bước quy hoạch động:
Ở bước 4, xét số $i$: nếu không lấy thì số cách là $F[i-1][j]$; nếu lấy số $i$ (chỉ được khi $i \le j$) thì phần còn lại phải có tổng $j - i$ từ các số $1..i-1$, số cách là $F[i-1][j-i]$. Cộng 2 trường hợp lại:
- Nếu $i \gt j$: $F[i][j] = F[i-1][j]$
- Nếu $i \le j$: $F[i][j] = F[i-1][j] + F[i-1][j-i]$
Minh hoạ: lấp đầy bảng F
Các bạn nhập $n$ rồi bấm Tiếp. Ô vàng là ô đang tính, các ô tím ở hàng trên là $F[i-1][j]$ và $F[i-1][j-i]$ được cộng lại. Ở bước cuối mình liệt kê luôn các cách chia (với $n$ nhỏ):
Và đây là source code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll powMod(ll a, ll b, ll m) {
if(b == 0) {
return 1;
}
ll half = powMod(a, b / 2, m);
half = (half * half) % m;
if(b % 2) {
return (half * (a % m)) % m;
}
return half;
}
ll f[505][500 * 501 / 4 + 5];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
ll sum = (n * (n + 1)) / 2;
if(sum % 2) {
cout << 0;
return 0;
}
sum /= 2;
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= sum; ++j) {
if(j < i) {
f[i][j] = f[i - 1][j];
}
else {
f[i][j] = f[i - 1][j] + f[i - 1][j - i];
}
f[i][j] %= mod;
}
}
ll res = (f[n][sum] * powMod(2, mod - 2, mod)) % mod;
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10000)
mod = 10**9 + 7
def powMod(a, b, m):
if b == 0:
return 1
half = powMod(a, b // 2, m)
half = (half * half) % m
if b % 2:
return (half * (a % m)) % m
return half
n = int(input())
s = (n * (n + 1)) // 2
if s % 2:
print(0)
sys.exit(0)
s //= 2
f = [[0] * (s + 1) for _ in range(n + 1)]
f[0][0] = 1
for i in range(1, n + 1):
for j in range(0, s + 1):
if j < i:
f[i][j] = f[i - 1][j]
else:
f[i][j] = f[i - 1][j] + f[i - 1][j - i]
f[i][j] %= mod
res = (f[n][s] * powMod(2, mod - 2, mod)) % mod
print(res)Giải thích 1 số chỗ trong code ở trên:
ll f[505][500 * 501 / 4 + 5];ta cần mảng 2 chiều $F[n + 1][sum + 1]$ với $sum = n(n+1)/4$. Mình khai báo mảng toàn cục để tránh tràn bộ nhớ stack: khi mảng tĩnh có số lượng phần tử $\gt 2 \cdot 10^5$ thì anh em nên dùng vector hoặc để biến toàn cục nha. $505 = 500 + 5$ (mình thường cộng thêm 5 cho chắc), $500 \cdot 501 / 4 + 5$ chính là $n(n+1)/4$ cộng thêm 5. Mảng toàn cục còn được tự khởi tạo toàn số $0$, đúng như bài toán cơ sở cần.ll res = (f[n][sum] * powMod(2, mod - 2, mod)) % mod;chính là số tập con có tổng $sum$ nhân với $2^{-1} \bmod mod$ =powMod(2, mod - 2, mod), rồi lấy tất cả chia dư cho $mod$.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O\big((n + 5) \cdot (n(n+1)/4 + 5)\big)$ vì ta chỉ dùng một mảng $F$. Với $n = 500$ là khoảng $505 \cdot 62630 \approx 3.2 \cdot 10^7$ số
long long, tầm 253 MB – vẫn trong giới hạn 512 MB của đề nhưng khá "nặng". - Thời gian: $O\big(n \cdot n(n+1)/4\big)$ vì phải lấp đầy mảng $F$, cộng thêm $O(\log mod)$ cho
powMod. Với $n = 500$ mất tầm $3.14 \cdot 10^7$ phép tính, trường hợp xấu nhất khoảng 0.3 đến 0.4 giây, vẫn dưới 1 giây.
Cách 2Quy hoạch động mảng 1 chiều – ít bộ nhớ, chạy nhanh hơn
Để ý hàng $i$ của bảng chỉ dùng tới hàng $i - 1$. Vậy ta có cách dùng ít bộ nhớ hơn: chỉ tạo mảng $F[n(n+1)/4 + 1]$. Trường hợp cơ sở $F[0] = 1$, và công thức truy hồi:
Mảng $F$ khai báo toàn cục để lúc đầu toàn bộ phần tử bằng $0$.
Cách này không chỉ ít bộ nhớ hơn mà cũng chạy nhanh hơn, dù độ phức tạp thời gian vẫn là $O\big(n \cdot n(n+1)/4\big)$. Vì với mảng 2 chiều toàn cục rất to, ta tốn thêm thời gian khởi tạo và truy cập bộ nhớ; chưa kể vòng $j$ ở cách 1 đi từ $0$ đến $sum$, còn ở đây chỉ đi từ $sum$ về $i$. Nhìn chung từ phân tích và lúc nộp bài thì cách này nhanh hơn nha.
Minh hoạ: cập nhật mảng 1 chiều
Sau đây là source code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll powMod(ll a, ll b, ll m) {
if(b == 0) {
return 1;
}
ll half = powMod(a, b / 2, m);
half = (half * half) % m;
if(b % 2) {
return (half * (a % m)) % m;
}
return half;
}
ll f[500 * 501 / 4 + 5];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
ll sum = (n * (n + 1)) / 2;
if(sum % 2) {
cout << 0;
return 0;
}
sum /= 2;
f[0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = sum; j >= i; --j) {
f[j] += f[j - i];
f[j] %= mod;
}
}
ll res = (f[sum] * powMod(2, mod - 2, mod)) % mod;
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10000)
mod = 10**9 + 7
def powMod(a, b, m):
if b == 0:
return 1
half = powMod(a, b // 2, m)
half = (half * half) % m
if b % 2:
return (half * (a % m)) % m
return half
n = int(input())
s = (n * (n + 1)) // 2
if s % 2:
print(0)
sys.exit(0)
s //= 2
f = [0] * (s + 1)
f[0] = 1
for i in range(1, n + 1):
for j in range(s, i - 1, -1):
f[j] += f[j - i]
f[j] %= mod
res = (f[s] * powMod(2, mod - 2, mod)) % mod
print(res)Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ còn $O\big(n(n+1)/4\big) = O(n^2)$ cho mảng $F$ (khoảng $62630$ số với $n = 500$, chỉ cỡ 0.5 MB).
- Thời gian: vẫn là $O\big(n \cdot n(n+1)/4\big)$, nhưng hằng số nhỏ hơn cách 1.
- 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