Hướng dẫn giải của Tích dãy
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ố dãy ~n~ số nguyên dương có tích bằng ~m~ (modulo ~10^9+7~). Mỗi phần tử của dãy là một ước của ~m~.
Sub 1: Vét cạn đệ quy — dùng khi ~n \le 3, m \le 10^4~
Gọi ~f(k, x)~ là số dãy ~k~ phần tử có tích ~x~. Thử phần tử đầu là mọi ước ~d~ của ~x~: ~f(k, x) = \sum_{d \mid x} f(k-1, x/d)~, với ~f(1, x) = 1~. Nếu chỉ nộp sub này: đúng 6/10 test.
Sub 2: Quy hoạch động trên các ước của m — ~O(n \cdot d(m)^2)~, dùng khi ~n \le 30~
Chỉ các ước của ~m~ (tối đa vài trăm) mới xuất hiện làm tích riêng. Giữ mảng ~dp[i]~ = số dãy ~k~ phần tử có tích bằng ước thứ ~i~, chuyển từ ~k-1~ sang ~k~ bằng tổng theo các ước. Nếu chỉ nộp sub này: đúng 10/10 test (trong bộ test này ~m~ có ít ước), nhưng với ~n~ lớn và ~m~ nhiều ước thì sẽ chậm.
Sub 3: Tổ hợp — ~O(\sqrt{m} + n)~
Phân tích ~m = p_1^{e_1} \cdots p_r^{e_r}~. Mỗi số nguyên tố độc lập: chia ~e~ đơn vị số mũ vào ~n~ vị trí có ~\binom{e+n-1}{e}~ cách (chia kẹo Euler). Đáp án là tích các giá trị đó modulo ~10^9+7~, tính giai thừa và nghịch đảo giai thừa (mũ ~e \le 20~ nên mảng cỡ ~n+40~ là đủ). Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Main đọc ~n, m~ từ file CAU4.INP (máy chấm dùng tên này dù đề ghi CAU3); ~n, m~ nhỏ gọi sub1, ~n \le 30~ gọi sub2, còn lại gọi sub3. 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.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, m;
// Sub 1: vét cạn đệ quy — f(k, x) = tổng f(k-1, x/d) theo các ước d của x.
// Dùng khi n <= 3, m <= 10^4
long long f(int k, int x) {
if (k == 1) return 1;
long long res = 0;
for (int d = 1; d <= x; d++) if (x % d == 0) res += f(k - 1, x / d);
return res % MOD;
}
void sub1() {
printf("%lld\n", f(n, m));
}
// Sub 2: quy hoạch động trên các ước của m: dp[i] = số dãy k phần tử có tích bằng ước thứ i.
// Mỗi bước k: nx[i] = tổng dp[idx(dv[i]/d)] theo các ước d của dv[i]. O(n * d(m)^2), dùng khi n <= 30
void sub2() {
vector<int> dv;
for (int d = 1; d <= m; d++) if (m % d == 0) dv.push_back(d);
int D = dv.size();
vector<vector<int>> pos(D); // pos[i] = chỉ số các thương dv[i]/d
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
if (dv[i] % dv[j] == 0)
pos[i].push_back(lower_bound(dv.begin(), dv.end(), dv[i] / dv[j]) - dv.begin());
vector<long long> dp(D, 1), nx(D); // k = 1: dãy (x) có tích x
for (int k = 2; k <= n; k++) {
for (int i = 0; i < D; i++) {
long long s = 0;
for (int p : pos[i]) s += dp[p];
nx[i] = s % MOD;
}
dp = nx;
}
printf("%lld\n", dp[D - 1]);
}
// Sub 3: tổ hợp. Phân tích m = p1^e1 * ... ; mỗi số nguyên tố chia e vào n vị trí độc lập:
// C(e+n-1, n-1) cách. Đáp án là tích các tổ hợp. O(sqrt(m) + (n+log m))
long long power(long long b, long long e) {
long long r = 1; b %= MOD;
for (; e; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
void sub3() {
int N = n + 40;
vector<long long> fact(N + 1, 1), inv(N + 1);
for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2);
for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
auto C = [&](int a, int b) { return fact[a] * inv[b] % MOD * inv[a - b] % MOD; };
long long res = 1;
int x = m;
for (int p = 2; (long long)p * p <= x; p++) if (x % p == 0) {
int e = 0;
while (x % p == 0) { x /= p; e++; }
res = res * C(e + n - 1, e) % MOD;
}
if (x > 1) res = res * C(n, 1) % MOD; // số nguyên tố còn lại, mũ 1
printf("%lld\n", res);
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
scanf("%d %d", &n, &m);
if (n <= 3 && m <= 10000) sub1();
else if (n <= 30) sub2();
else sub3();
return 0;
}
Bình luận