Hướng dẫn cho LQDOJ CUP 2022 - Round 2 - NUMCITIES
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(40\%\) số điểm): \(n \leq 10^3\).
Tutorial
Duyệt qua \(O(n)\) giá trị của \(a\) và \(O(n)\) giá trị của \(d\).
Nhận thấy độ dài dãy tối đa là: \(t = \left\lfloor\frac{n-a}{d}\right\rfloor + 1\) vì các giá trị nằm trong đoạn \([0,n]\).
Vậy, với cặp \((a,d)\) bất kì, ta cộng vào đáp án một lượng \(t-1\) (có \(t\) dãy cấp số cộng với độ dài lần lượt là \(1,2,3,\dots,t\)). Các dãy độ dài \(1\) được xét riêng.
Độ phức tạp: \(\mathcal{O}(q \times n^2)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, numQuery;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NUMCITIES.inp", "r", stdin);
freopen("NUMCITIES.out", "w", stdout);
cin >> numQuery;
while (numQuery--) {
cin >> n;
long long result = 0;
for (int a = 0; a <= n; a++) {
result++;
for (int d = 1; d <= n; d++) {
result += (n - a) / d;
}
}
cout << result % MOD << '\n';
}
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^6\).
Tutorial
Nhắc lại, ở subtask 1, với \((a,d)\) bất kì, ta cộng vào đáp án \(\left\lfloor\frac{n-a}{d}\right\rfloor\).
Ta cố giảm thiểu độ phức tạp bằng cách chỉ duyệt \(O(n)\) giá trị của \(d\). Có thể tính được tổng trên mà không cần duyệt \(a\) hay không?
Giả sử \(N = kd + r\) (\(0 \le r < d\)). Quan sát:
- Với \(0 \le a \le r \rightarrow\) cộng vào \(k \Rightarrow\) tổng cộng vào là \(k(r+1)\)
- Với \(r < a \le r + d \rightarrow\) cộng vào \(k-1 \Rightarrow\) tổng cộng vào là \((k-1)d\)
- Với \(r + d < a \le r + 2d \Rightarrow\) tổng cộng vào là \((k-2)d\)
- \(\ldots\)
- Với \(r + d\times (i - 1) < a \le r+d\times i \Rightarrow\) tổng cộng vào là \((k-i)d\)
Vậy với mỗi \(d\), hoàn toàn tính được tổng của các cặp \((a,d)\) trong \(O(1)\).
Độ phức tạp: \(\mathcal{O}(q \times n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int numQuery;
long long n;
int prod(long long a, long long b) {
return 1LL * (a % MOD) * (b % MOD) % MOD;
}
int sum(long long n) {
long long a[2] = {n, n + 1};
a[n % 2] /= 2;
return prod(a[0], a[1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NUMCITIES.inp", "r", stdin);
freopen("NUMCITIES.out", "w", stdout);
cin >> numQuery;
while (numQuery--) {
cin >> n;
long long answer = (n + 1) % MOD;
for (int d = 1; d <= n; d++) {
int r = n % d;
long long k = n / d;
answer += prod(r + 1, k);
answer += prod(sum(k - 1), d); // < (10^6)^3
answer %= MOD;
}
cout << answer << '\n';
}
return 0;
}
Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Ta giải bằng chia căn.
Nhận xét: Công bội càng lớn thì độ dài tối đa của dãy cấp số cộng càng bé. Với \(d > \sqrt{n}\), độ dài của dãy cấp số cộng có công bội \(d\) không vượt quá \(\sqrt{n}\).
Đặt \(R = \left\lfloor\sqrt{n}\right\rfloor\). Ta chia làm hai trường hợp:
- \(d \le R\). Tiến hành duyệt \(d\) và giải như subtask 2
- \(d > R\), ta kết luận độ dài dãy \(<R\).
Ta tiến hành duyệt độ dài dãy, đặt là \(l,\) \(l \in [1,R-1]\). Cần trả lời câu hỏi: "Có bao nhiêu dãy cấp số cộng có độ dài \(l\)?"
Nhận thấy với cấp số cộng có độ dài \(l\), công bội \(d\) thì hiệu giữa giá trị cuối và giá trị đầu là \(d(l-1)\). Vì các giá trị giới hạn trong \([0,n]\) nên sẽ có \(n-d(l-1)+1\) dãy cấp số cộng như vậy.
Vì thế, nếu cố định \(l\) thì ta hoàn toàn tính được công bội lớn nhất có thể: \(d_{max} = \left\lfloor\frac{n}{l-1}\right\rfloor)\).
Tổng \(\sum_{d = R+1}^{d_{max}} n-d(l-1)+1\) tính được trong \(O(1)\).
Độ phức tạp: \(\mathcal{O}(q \times \sqrt{n})\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int numQuery;
long long n;
int prod(long long a, long long b) {
return 1LL * (a % MOD) * (b % MOD) % MOD;
}
int sum(long long n) {
long long a[2] = {n, n + 1};
a[n % 2] /= 2;
return prod(a[0], a[1]);
}
int subtask2(long long n, int lim = -1) {
if (lim < 0) {
lim = n;
}
long long result = (n + 1) % MOD;
for (int d = 1; d <= lim; d++) {
int r = n % d;
long long k = n / d;
result += prod(r + 1, k);
result += prod(sum(k - 1), d);
result %= MOD;
}
return result;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NUMCITIES.inp", "r", stdin);
freopen("NUMCITIES.out", "w", stdout);
cin >> numQuery;
while (numQuery--) {
cin >> n;
long long answer = 0;
const int R = sqrt(n);
answer += subtask2(n, R);
for (int l = 2; l <= n / R; l++) {
long long dmax = n / (l - 1);
if (dmax <= R) {
continue;
}
answer += prod(n, (dmax - R));
answer -= prod(l - 1, sum(dmax) - sum(R) + MOD);
answer += dmax - R;
answer %= MOD;
}
if (answer < 0) {
answer += MOD;
}
cout << answer << '\n';
}
return 0;
}
Bình luận