Hướng dẫn giải của QUA SÔNG
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số cách đi từ hòn đá 1 đến hòn đá ~N~, mỗi bước nhảy có độ dài ~d~ là ước của một trong ~K~ số ~a_i~. ~dp[x]~ là số cách đến hòn đá ~x~: ~dp[1]=1~, ~dp[x] = \sum dp[x-d]~ với ~d~ hợp lệ, ~d < x~; lấy dư ~10^9+7~.
Sub 1: Quy hoạch động vét cạn — ~O(N^2 \cdot K)~, dùng khi ~N \le 5000~
Với mỗi ~x~ thử mọi ~d < x~, kiểm tra ~d~ có là ước của ~a_i~ nào không. Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Liệt kê trước các ước — ~O(N \cdot D)~
Tập các độ dài bước hợp lệ chỉ gồm các ước của ~a_i \le 10^6~, mỗi số có tối đa 240 ước nên tổng ~D~ không quá khoảng 2400. Liệt kê các ước một lần (duyệt đến căn ~a_i~), rồi với mỗi ~x~ chỉ duyệt các ước. Nộp riêng sub này đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu, nếu ~N \le 5000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, k;
int a[15];
static bool allowed[1000005];
long long dp[1000005];
// Sub 1: dp O(N^2): d hợp lệ nếu d là ước của một a_i
void sub1() {
dp[1] = 1;
for (int x = 2; x <= n; x++) {
long long s = 0;
for (int d = 1; d < x; d++) {
bool ok = false;
for (int i = 1; i <= k; i++) if (a[i] % d == 0) ok = true;
if (ok) s += dp[x - d];
}
dp[x] = s % MOD;
}
cout << dp[n] << "\n";
}
// Sub 2: liệt kê trước tập các ước (không quá ~2400 giá trị), dp O(N * số ước)
void sub2() {
vector<int> ds;
for (int i = 1; i <= k; i++)
for (int d = 1; (long long)d * d <= a[i]; d++)
if (a[i] % d == 0) {
allowed[d] = allowed[a[i] / d] = true;
}
for (int d = 1; d <= 1000000; d++) if (allowed[d]) ds.push_back(d);
dp[1] = 1;
for (int x = 2; x <= n; x++) {
long long s = 0;
for (int d : ds) {
if (d >= x) break;
s += dp[x - d];
}
dp[x] = s % MOD;
}
cout << dp[n] << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= k; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận