Đếm Phép Nhân (Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 3)
Đề bài
Câu 3. ĐẾM PHÉP NHÂN (6 điểm)
| Mã nguồn | Dữ liệu vào | Dữ liệu ra | Thời gian | Bộ nhớ |
|---|---|---|---|---|
MCOUNT.* | MCOUNT.inp | MCOUNT.out | 1 giây | 1024 MB |
Quang có một dãy số nguyên dương $a_1, a_2, \ldots, a_n$. Quang đố Linh viết một chương trình đếm số lượng dãy con $b_1, b_2, \ldots, b_k$ của $a$ sao cho tích $b_1 \times b_2 \times \ldots \times b_k$ không vượt quá một số $x$ cố định.
Do Linh mới học lập trình nên chương trình của Linh phải mất 69420ms mới có thể đưa ra kết quả. Liệu bạn có thể viết một chương trình chỉ chạy trong 694ms hay không?
Nhắc lại: một dãy $b$ là một dãy con của dãy $a$ khi và chỉ khi có thể xóa một số phần tử trong $a$ và giữ nguyên thứ tự các phần tử còn lại để thu được dãy $b$.
Yêu cầu: Bạn hãy viết một chương trình kiểm tra xem kết quả chương trình của Linh đưa ra có đúng hay không.
Dữ liệu vào: Nhập từ file MCOUNT.inp:
- Dòng đầu tiên gồm hai số nguyên dương $n, x$ $(1 \le n \le 10^5,\ 1 \le x \le 2 \times 10^5)$.
- Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le x)$.
Dữ liệu ra: Ghi ra file MCOUNT.out:
- Một dòng duy nhất là số lượng dãy con thỏa mãn. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho $10^9 + 7$.
Ràng buộc bổ sung:
- $20\%$ số điểm có $n \le 20$.
- $20\%$ số điểm khác có $a_i = 1$.
- $20\%$ số điểm khác có $n, x \le 5000$.
- $15\%$ số điểm khác có $a_i$ là lũy thừa của $2$.
- $15\%$ số điểm khác có $a_i = i$.
- $10\%$ số điểm còn lại không có giới hạn gì thêm.
Lưu ý: đề gốc đọc/ghi file MCOUNT.inp / MCOUNT.out; nộp trên web (SQRTOJ) thì đọc từ bàn phím và in ra màn hình. Code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng.
4 6
2 3 3 46Giải thích (theo đề): Các dãy con thỏa mãn là:
- 1 phần tử: $(2), (3), (3), (4)$.
- 2 phần tử: $(2, 3), (2, 3)$.
Không có dãy con có 3 hoặc 4 phần tử nào thỏa mãn điều kiện.
Lời mở đầu
Đây là bài 3 ngày thi thứ nhất trong đợt thi thử HSG lớp 9 năm 2025 của câu lạc bộ SQRT. Đề có tới 6 subtask, mỗi subtask lại "gợi ý" một hướng đi khác nhau: duyệt bitmask, đếm tập con, quy hoạch động, bài toán cái túi, duyệt bội số và cuối cùng là kỹ thuật chia căn. Vì vậy mình viết lời giải theo đúng từng subtask để các bạn thấy được tư duy đi lên từng nấc nha. Bạn Linh mất 69420ms, mình với các bạn cố gắng xuống dưới 694ms nhé 😆. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Điểm quan trọng nhất: dãy con được phân biệt theo vị trí, không phải theo giá trị. Dãy $a = (2, 3, 3, 4)$ có hai số $3$ ở vị trí 2 và 3, nên $(3)$ được đếm 2 lần, $(2, 3)$ cũng được đếm 2 lần. Nói cách khác, ta đang đếm số tập con khác rỗng các chỉ số sao cho tích các phần tử tương ứng không vượt quá $x$. Thứ tự trong dãy con không ảnh hưởng tới tích, nên ta cứ nghĩ theo kiểu "chọn hay không chọn từng phần tử" là được.
| Dãy con (theo vị trí) | Tích | $\le 6$? |
|---|---|---|
| (2) · (3)vt 2 · (3)vt 3 · (4) | 2 · 3 · 3 · 4 | Có, 4 dãy |
| (2, 3)vt 1,2 · (2, 3)vt 1,3 | 6 · 6 | Có, 2 dãy |
| (2, 4) · (3, 3) · (3, 4) · (3, 4) | 8 · 9 · 12 · 12 | Không |
| Các dãy 3, 4 phần tử | $\ge 18$ | Không |
Tổng cộng $4 + 2 = 6$ dãy con.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Duyệt mọi dãy con bằng bitmask – O(2ⁿ · n)
Với $n \le 20$, số dãy con khác rỗng là $2^n - 1 \approx 10^6$, đủ nhỏ để thử hết. Ta sẽ duyệt hết tất cả cách chọn dãy (không rỗng) có thể và kiểm tra xem tích của nó có nhỏ hơn hoặc bằng $x$ hay không.
Cách liệt kê quen thuộc là dùng bitmask: mỗi số $j$ từ $1$ đến $2^n - 1$ ứng với một dãy con, bit thứ $i$ của $j$ bằng $1$ nghĩa là có chọn phần tử $a_{i+1}$. Hàm testBit(j, i) trả về bit thứ $i$ của $j$ bằng phép j & (1 << i).
break luôn – vừa đỡ tốn thời gian, vừa đảm bảo $g$ không bao giờ lớn quá $x \cdot \max a_i \le 4 \cdot 10^{10}$ (vẫn vừa long long). Cuối cùng nếu $g \le x$ thì tăng biến đếm sl.Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
long long MOD = 1e9 + 7;
bool testBit(int x, int k){
return x & (1 << k);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
long long sl = 0;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int j = 1; j < (1 << n); j ++){
int g = 1;
for (int i = 0; i < n; i ++){
if (testBit(j, i)) g *= a[i + 1];
if (g > x) break;
}
if (g <= x) sl ++;
}
cout << sl;
}import sys, os
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
sl = 0
for j in range(1, 1 << n):
g = 1
for i in range(n):
if (j >> i) & 1:
g *= a[i + 1]
if g > x:
break
if g <= x:
sl += 1
print(sl)
main()
sys.stdout.flush()Ở subtask này kết quả không vượt quá $2^{20}$ nên chưa cần chia lấy dư. Các bạn bấm Tiếp để chạy tay từng dòng nha, phần "Dữ liệu" tô xanh những phần tử đang được chọn trong mặt nạ $j$:
Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ lưu mảng $a$: $O(n)$.
- Thời gian: có $2^n$ mặt nạ, mỗi mặt nạ duyệt tối đa $n$ bit: $O(2^n \cdot n)$. Với $n = 20$ là khoảng $2 \cdot 10^7$ phép tính, ổn.
Subtask 2Tất cả aᵢ = 1 – đáp án là 2ⁿ − 1
Nếu tất cả các $a_i = 1$, thì có nghĩa là tất cả những tập con không rỗng có thể thu được từ $a$ đều thoả mãn yêu cầu đề bài, vì tích của chúng luôn bằng $1$ nên không quá $x$. Như vậy, ta chỉ cần tính số tập con không rỗng của $a$.
Giả sử ta đã có được số lượng tập con thu được từ $i - 1$ phần tử đầu, khi duyệt đến phần tử thứ $i$ sẽ có hai trường hợp:
- Không chứa phần tử thứ $i$.
- Chứa phần tử thứ $i$.
Do mỗi tập cũ có hai lựa chọn nên số tập con thu được từ $i$ phần tử đầu sẽ gấp đôi số tập con thu được từ $i - 1$ phần tử đầu. Bắt đầu với $1$ (tập rỗng), sau $n$ lần gấp đôi ta có $2^n$ tập con.
(sl - 1 + MOD) % MOD để phòng trường hợp sl sau khi lấy dư bằng $0$ thì trừ $1$ sẽ ra số âm.Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
long long MOD = 1e9 + 7;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
long long sl = 1;
for (int i = 1; i <= n; i ++){
cin >> a[i];
sl *= 2;
sl %= MOD;
}
cout << (sl - 1 + MOD) % MOD << endl;
}import sys, os
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
MOD = 10**9 + 7
sl = 1
for i in range(n):
sl = sl * 2 % MOD
print((sl - 1 + MOD) % MOD)
main()
sys.stdout.flush()Subtask 3Quy hoạch động f[i][j] – O(n · x)
Ở subtask này $n, x \le 5000$, ta có thể dùng một bảng quy hoạch động kích thước $n \times x$.
Khi xét tới phần tử thứ $i$, có công thức truy hồi sau:
- Cách chọn tập không chứa phần tử $i$: tích vẫn là $j$, có $f[i - 1][j]$ cách.
- Cách chọn tập chứa phần tử $i$: chỉ có thể khi $j$ chia hết cho $a_i$, khi đó phần còn lại phải có tích $\dfrac{j}{a_i}$, có $f[i - 1]\left[\dfrac{j}{a_i}\right]$ cách.
Đáp án là $\left(\sum_{j=1}^{x} f[n][j]\right) - 1$ (trừ đi tập rỗng nằm trong $f[n][1]$). Vì sao chỉ cần $j \le x$? Vì ta chỉ quan tâm những tích không vượt quá $x$, và một tập có tích $\gt x$ thì thêm phần tử nào vào (đều $\ge 1$) cũng vẫn $\gt x$, nên bỏ qua hoàn toàn được.
Các bạn nhập thử dữ liệu nhỏ vào khung minh hoạ dưới đây và bấm Tiếp: mỗi bước điền thêm một hàng của bảng $f$, ô xanh là ô được "cộng thêm" nhờ lấy phần tử $a_i$, ô tím ở hàng trên là ô nguồn $f[i-1][j / a_i]$:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
int f[5005][5005];
long long MOD = 1e9 + 7;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
long long sl = 0;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
f[0][1] = 1;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= x; j ++){
f[i][j] = f[i - 1][j];
if (j % a[i] == 0) f[i][j] += f[i - 1][j / a[i]];
f[i][j] %= MOD;
}
}
for (int i = 1; i <= x; i ++){
sl += f[n][i];
sl %= MOD;
}
cout << (sl - 1 + MOD) % MOD << endl;
}import sys, os
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
MOD = 10**9 + 7
# prev = f[i - 1][...], cur = f[i][...]
prev = [0] * (x + 1)
prev[1] = 1
for i in range(1, n + 1):
cur = prev[:] # f[i][j] = f[i-1][j]
ai = a[i]
for j in range(ai, x + 1, ai): # chỉ những j chia hết cho a[i]
cur[j] = (cur[j] + prev[j // ai]) % MOD
prev = cur
sl = sum(prev[1:]) % MOD
print((sl - 1 + MOD) % MOD)
main()
sys.stdout.flush()Bản Python mình chỉ giữ 2 hàng (hàng trước và hàng hiện tại), và chỉ duyệt các $j$ là bội của $a_i$ vì những ô khác chỉ đơn giản là chép từ hàng trên xuống – cho nhanh hơn chứ công thức y hệt bản C++.
Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng $f$ có $(n + 1) \times (x + 1)$ ô: $O(n \cdot x)$. Khai báo
long long f[5005][5005]tốn khoảng 200 MB, vẫn nằm trong giới hạn 1024 MB của đề. - Thời gian: mỗi ô tính $O(1)$: $O(n \cdot x) = 2.5 \cdot 10^7$ phép tính với $n = x = 5000$.
Subtask 4aᵢ là lũy thừa của 2 – quy về bài toán cái túi, O(n · log x)
Nhận xét rằng, khi mọi $a_i = 2^{e_i}$ thì tích của một tập con bây giờ sẽ có dạng
Ta gọi $cnt$ là số lớn nhất sao cho $2^{cnt} \le x$ (với $x \le 2 \cdot 10^5$ thì $cnt \le 17$). Lúc này ta cần đếm số lượng tập con sao cho tích là $2^s$ mà $s \le cnt$. Nhận thấy rằng, khi ta đang có một tập con và nhân thêm một số nào đó trong mảng để tạo thêm tập con mới, số mũ trên tích sẽ thay đổi theo phép cộng. Tới đây, chúng ta sẽ quy về bài toán cái túi: mảng $a$ sẽ được đặt lại thành $a_i = e_i$ (số mũ), và ta tính số lượng tập con từ $a$ sao cho tổng nhỏ hơn hoặc bằng $cnt$.
$f[i][j] = f[i-1][j] + f[i-1][j - e_i]$ (nếu $j \ge e_i$). Đáp án: $\sum_{j=0}^{cnt} f[n][j] - 1$.
Trong code, mảng q dùng để đổi nhanh $2^k \to k$: vòng lặp đầu tiên gán q[1] = 0, q[2] = 1, q[4] = 2, … cho mọi lũy thừa của 2 không vượt quá $x$, đồng thời đếm luôn $cnt$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
int f[100005][20];
int q[200005];
long long MOD = 1e9 + 7;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
long long sl = 1, cnt = 0;
for (; sl <= x; sl *= 2){
q[sl] = cnt;
cnt ++;
}
cnt --;
for (int i = 1; i <= n; i ++){
cin >> a[i];
a[i] = q[a[i]];
}
f[0][0] = 1;
for (int i = 1; i <= n; i ++){
for (int j = 0; j <= cnt; j ++){
f[i][j] = f[i - 1][j];
if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
f[i][j] %= MOD;
}
}
sl = 0;
for (int j = 0; j <= cnt; j ++){
sl += f[n][j];
sl %= MOD;
}
cout << (sl - 1 + MOD) % MOD << endl;
}import sys, os
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
MOD = 10**9 + 7
q = {}
sl, cnt = 1, 0
while sl <= x:
q[sl] = cnt
cnt += 1
sl *= 2
cnt -= 1
a = [0] + [q.get(int(v), 0) for v in data[2:2 + n]]
prev = [0] * (cnt + 1)
prev[0] = 1
for i in range(1, n + 1):
cur = prev[:]
for j in range(a[i], cnt + 1):
cur[j] = (cur[j] + prev[j - a[i]]) % MOD
prev = cur
sl = sum(prev) % MOD
print((sl - 1 + MOD) % MOD)
main()
sys.stdout.flush()Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng $f$ có $(n + 1) \times (cnt + 1)$ ô với $cnt \le 17$: $O(n \cdot \log x)$.
- Thời gian: $O(n \cdot \log x)$, khoảng $1.8 \cdot 10^6$ phép tính.
Subtask 5aᵢ = i – QHĐ một chiều, chỉ duyệt bội số, O(x · log x)
Quay lại công thức của subtask 3: ta gọi $f[i][j]$ là số lượng tập con có thể tạo được từ $i$ phần tử đầu và có tích bằng $j$.
Ta nhận thấy rằng, giữa $f[i][j]$ và $f[i - 1][j]$ chỉ có thể xảy ra thay đổi khi $j$ chia hết cho $a_i$, vì như vậy mới có thể tồn tại các tập con sử dụng phần tử thứ $i$ để tạo ra tích $j$. Trường hợp $j$ không chia hết cho $a_i$, ta dễ dàng thấy cách tạo $f[i][j]$ sẽ tương đương với $f[i-1][j]$ (không thay đổi), vì nếu còn tồn tại $a_i$ trong tập con được tạo thì tích phải chia hết cho $a_i$ (vô lý).
$f_{\text{mới}}[j] = f_{\text{cũ}}[j] + f_{\text{cũ}}\!\left[\dfrac{j}{a_i}\right]$
Trong subtask này $a_i = i$ nên code dùng luôn $i$ thay cho $a_i$.
Có một chi tiết rất quan trọng: vòng lặp phải duyệt $j$ từ lớn về nhỏ (j = x - x % i là bội lớn nhất của $i$ không vượt $x$, rồi giảm dần j -= i). Vì $\dfrac{j}{i} \lt j$, khi duyệt giảm dần thì lúc cập nhật $f[j]$, ô $f[j / i]$ chưa bị cập nhật ở lượt này – tức vẫn là giá trị cũ $f_{\text{cũ}}$, đúng như công thức. Nếu duyệt tăng dần, $f[j / i]$ có thể đã được cộng thêm ở lượt này, nghĩa là phần tử $a_i$ bị dùng 2 lần – sai! Đây chính là mẹo quen thuộc của bài toán cái túi 0/1 dùng mảng một chiều.
Còn với $i = 1$ thì $j / i = j$: lệnh f[j] += f[j] đơn giản là nhân đôi $f[j]$ – đúng vì lấy hay không lấy số 1 tích vẫn vậy.
Các bạn xem khung minh hoạ: ô vàng là ô $f[j]$ đang cập nhật, ô tím là ô nguồn $f[j / i]$, ô xanh là các bội đã cập nhật xong trong lượt hiện tại:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
int f[200005];
long long MOD = 1e9 + 7;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
f[1] = 1;
for (int i = 1; i <= n; i ++){
for (int j = x - (x % i); j >= i; j -= i){
f[j] += f[j / i];
f[j] %= MOD;
}
}
int sl = 0;
for (int j = 1; j <= x; j ++){
sl += f[j];
sl %= MOD;
}
cout << (sl - 1 + MOD) % MOD << endl;
}import sys, os
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
MOD = 10**9 + 7
f = [0] * (x + 1)
f[1] = 1
for i in range(1, n + 1):
for j in range(x - x % i, i - 1, -i):
f[j] = (f[j] + f[j // i]) % MOD
sl = sum(f[1:]) % MOD
print((sl - 1 + MOD) % MOD)
main()
sys.stdout.flush()Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $f$ một chiều: $O(x)$.
- Thời gian: với mỗi $i$ chỉ duyệt $\dfrac{x}{i}$ bội số, tổng cộng $\dfrac{x}{1} + \dfrac{x}{2} + \ldots + \dfrac{x}{n} \approx x \ln n$. Chứng minh được khi duyệt bội thì độ phức tạp sẽ không quá $O(x \log x)$ (tổng điều hoà) – khoảng $2.4 \cdot 10^6$ phép tính với $x = 2 \cdot 10^5$.
Subtask 6Chia căn + tổ hợp – lời giải đầy đủ
Ta đặt $S = \lfloor \sqrt{2 \cdot 10^5} \rfloor = 447$ (trong code là biến cur).
Ta nhận thấy rằng, trong một tập con thoả mãn thì sẽ xuất hiện không quá một giá trị $a_i \gt S$, vì hai số lớn hơn $S$ nhân với nhau đã $\ge 448^2 = 200704 \gt 2 \cdot 10^5 \ge x$. Ta có hai trường hợp sau:
- Nếu tồn tại một số $a_i \gt S$ trong tập, thì tích các số còn lại sẽ không quá $\left\lfloor \dfrac{x}{a_i} \right\rfloor \lt S$. Khi này ta chỉ cần tìm số cách lấy một tập con từ các số $\le S$ sao cho tích không quá $\dfrac{x}{a_i}$.
- Nếu không tồn tại số nào lớn hơn $S$: các số trong tập đều không quá $S$, và việc ta cần là tính số cách lấy một tập con từ các số $\le S$ sao cho tích nhỏ hơn hoặc bằng $x$.
Tất cả những gì ta cần tính ở trên đều chỉ sử dụng đến những phần tử không quá $S$ – mà các giá trị này chỉ có $447$ loại! Thay vì xét từng phần tử như subtask 5 (bị chậm khi trùng nhiều), ta gom các phần tử cùng giá trị lại và xét theo từng giá trị.
$f[v][j \cdot v^l] \mathrel{+}= f[v - 1][j] \cdot C(cnt[v], l)$ với $l \ge 0$, $j \cdot v^l \le x$.
Vì $v \ge 2$ nên $v^l \le x \le 2 \cdot 10^5$ kéo theo $l \le 17$ ($2^{18} = 262144$): ta sẽ không bao giờ dùng quá $17$ phần tử có cùng giá trị $v$. Số tổ hợp $C(n, k)$ – số cách để chọn $k$ phần tử từ $n$ số – được tính trước bằng tam giác Pascal: $C(n, k) = C(n-1, k) + C(n-1, k-1)$ (lấy hoặc không lấy phần tử thứ $n$), chỉ cần $k \le 17$ nên bảng c[25][100005] là đủ.
Về cài đặt, code dùng 2 hàng f[0] (giá trị hiện tại, ứng với $f[v-1]$ rồi thành $f[v]$) và f[1] (phần cộng thêm khi lấy $l \ge 1$ số $v$). Trường hợp $l = 0$ chính là giữ nguyên f[0]. Sau khi tính hết phần cộng thêm vào f[1], ta cộng nó vào f[0] rồi xoá f[1] về $0$ – các tích mới đều là bội của $v$ nên chỉ cần duyệt j = v, 2v, 3v, ….
while (h <= x) sẽ chạy mãi). Gọi $c_1$ là số lượng phần tử có giá trị là $1$. Sau khi tính xong số lượng tập con thoả mãn điều kiện mà các phần tử không có giá trị $1$, ta thấy rằng việc thêm bao nhiêu số $1$ vào cũng không ảnh hưởng đến tích của tập con. Số cách thêm số $1$ vào sẽ là $2^{c_1}$ (biến sl trong code), ta sẽ nhân với kết quả ban đầu.Số $-1$ cuối cùng là để bỏ tập rỗng (nằm trong $f[1]$ với $0$ số $1$ nào được chọn). Các bạn thử khung minh hoạ dưới đây: để dễ nhìn với $x$ nhỏ, khung dùng ngưỡng $S = \lfloor \sqrt{x} \rfloor$ (vẫn đúng vì hai số lớn hơn $\sqrt{x}$ có tích vượt $x$); còn code dùng hẳn $447$ cho mọi $x$. Bảng hiện các tích $j$ đang có $f[j] \gt 0$:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
int a[100005];
int cur = sqrt(200000);
int f[2][200005];
int cnt[505];
int c[25][100005];
long long MOD = 1e9 + 7;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("MCOUNT.inp", "r")){
freopen("MCOUNT.inp", "r", stdin);
freopen("MCOUNT.out", "w", stdout);
}
cin >> n >> x;
long long sl = 1;
for (int i = 1; i <= n; i ++){
cin >> a[i];
if (a[i] > 1 && a[i] <= cur) cnt[a[i]] ++;
else if (a[i] == 1){
sl *= 2;
sl %= MOD;
}
}
c[0][0] = 1;
for (int j = 1; j <= n; j ++){
for (int k = 0; k <= min(17ll, j); k ++){
c[k][j] += c[k][j - 1];
if (k) c[k][j] += c[k - 1][j - 1];
c[k][j] %= MOD;
}
}
f[0][1] = 1;
for (int i = 2; i <= cur; i ++){
if (!cnt[i]) continue;
int h = i;
int l = 1;
while (h <= x){
for (int j = 1; j <= x / h; j ++){
f[1][h * j] += (f[0][j] * c[l][cnt[i]]);
f[1][h * j] %= MOD;
}
h *= i;
l ++;
}
for (int j = i; j <= x; j += i){
f[0][j] += f[1][j];
f[0][j] %= MOD;
f[1][j] = 0;
}
}
long long res = 0;
for (int i = 1; i <= n; i ++){
if (a[i] > cur){
for (int j = 1; j <= cur; j ++){
if (j * a[i] <= x){
res += ((long long) f[0][j] * sl) % MOD;
if (res >= MOD) res -= MOD;
}
}
}
}
for (int i = 1; i <= x; i ++){
res += (f[0][i] * sl) % MOD;
}
cout << (res - 1 + MOD) % MOD << endl;
}import sys, os
from math import isqrt
def main():
if os.path.exists('MCOUNT.inp'):
sys.stdin = open('MCOUNT.inp')
sys.stdout = open('MCOUNT.out', 'w')
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
a = [int(v) for v in data[2:2 + n]]
MOD = 10**9 + 7
cur = isqrt(200000)
cnt = [0] * (cur + 1)
sl = 1
big = []
for v in a:
if 1 < v <= cur:
cnt[v] += 1
elif v == 1:
sl = sl * 2 % MOD
else:
big.append(v)
# c[k][j] = C(j, k) với k <= 17
c = [[0] * (n + 1) for _ in range(18)]
c[0] = [1] * (n + 1)
for k in range(1, 18):
ck, cp = c[k], c[k - 1]
for j in range(k, n + 1):
ck[j] = (ck[j - 1] + cp[j - 1]) % MOD
f0 = [0] * (x + 1)
f1 = [0] * (x + 1)
f0[1] = 1
for i in range(2, cur + 1):
if not cnt[i]:
continue
h, l = i, 1
while h <= x:
w = c[l][cnt[i]] if l < 18 else 0
for j in range(1, x // h + 1):
f1[h * j] = (f1[h * j] + f0[j] * w) % MOD
h *= i
l += 1
for j in range(i, x + 1, i):
f0[j] = (f0[j] + f1[j]) % MOD
f1[j] = 0
# pre[t] = f0[1] + ... + f0[t] (thay cho vòng for j <= cur trong C++)
pre = [0] * (x + 1)
for t in range(1, x + 1):
pre[t] = (pre[t - 1] + f0[t]) % MOD
res = 0
for v in big:
res += pre[min(cur, x // v)] * sl
res += pre[x] * sl
print((res - 1) % MOD)
main()
sys.stdout.flush()Giải thích 1 số chỗ trong code ở trên:
- Vòng đọc dữ liệu: số $1$ thì nhân đôi
sl(để có $2^{c_1}$), số trong $[2, S]$ thì tăngcnt, còn số lớn hơn $S$ để nguyên trong mảnga, xử lý ở cuối. - Vòng
while (h <= x):hlần lượt là $v, v^2, v^3, \ldots$ vàllà số lượng số $v$ được lấy. Với mỗijmàh * j <= x, cộngf[0][j] * c[l][cnt[i]]vàof[1][h * j]. Nếu $l \gt cnt[v]$ thìc[l][cnt[v]] = 0nên tự động không cộng gì. - Phần số lớn: với mỗi $a_i \gt S$, cộng
f[0][j] * slvới mọi $j \le S$ mà $j \cdot a_i \le x$. Bản Python mình dùng mảng cộng dồnpređể lấy luôn tổng $f[1] + \ldots + f[\lfloor x / a_i \rfloor]$ thay vì vòng lặp 447 lần, cho Python đỡ chậm – kết quả y hệt. - Các phép nhân
f[0][j] * c[l][cnt[i]]có thể tới cỡ $10^{18}$ nên phải dùnglong long(code đã#define int long long).
Khung chạy tay bên dưới đi đúng thứ tự code. Vì vòng for i chạy tới $447$ và vòng cuối chạy tới $x$, mình gom lại những lượt "không làm gì" (giá trị $i$ không xuất hiện, hay ô $f = 0$ cộng thêm $0$) để các bạn đỡ phải bấm hàng trăm lần nha:
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $f$ cỡ $2 \times x$, bảng tổ hợp $18 \times n$: $O(x + n)$.
- Thời gian:
- Bảng tổ hợp: $O(17 \cdot n)$.
- Quy hoạch động: với mỗi giá trị $v \in [2, S]$ có xuất hiện, vòng
whileduyệt $\frac{x}{v} + \frac{x}{v^2} + \ldots \le \frac{x}{v - 1}$ ô, cộng thêm $\frac{x}{v}$ ô khi gộpf[1]vàof[0]. Tổng theo mọi $v$ là $O(x \log S)$ (lại là tổng điều hoà) – và điểm mấu chốt là không phụ thuộc số lần trùng nữa. - Phần số lớn: mỗi số lớn duyệt tối đa $S$ giá trị $j$: $O(n \cdot S) \approx 4.5 \cdot 10^7$ phép tính đơn giản.
- 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