Hướng dẫn cho LQDOJ CUP 2022 - Round 1 - SUMARR
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\) (\(30\%\) số điểm): \(n \leq 500\).
Tutorial
Với mỗi giá trị của \(U\) ta duyệt các cặp \(i, j\) \((0 \leq i, j < n)\) sao cho \((i \text{ or } j) \leq U\)
Độ phức tạp: \(\mathcal{O}\left(n^{3}\right)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
const int MOD = 1000000007;
int n;
int a[MAX_N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int u = 0; u < n; u++) {
long long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((i | j) <= u) {
(ans += a[i] * (long long)a[j]) %= MOD;
}
}
}
cout << ans << ' ';
}
return 0;
}
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\).
Tutorial
Ta có thể tính tổng \(a_i \cdot a_j\) với \((i \mid j) = U\) với \(0 \leq U < n\) và tổng tiền tố để có thể tính tổng \(\leq U\)
Duyệt trâu tất cả các cặp \(i\) và \(j\) sau đó cộng vào tổng \(sum[i \mid j]\) một lượng bằng \(a_i \cdot a_j\) và tổng tiền tố mảng \(sum\)
Độ phức tạp: \(\mathcal{O}\left(n^2\right)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
const int MOD = 1000000007;
int n;
long long arr[MAX_N];
long long prefixSum[MAX_N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
prefixSum[i | j] = (prefixSum[i | j] + arr[i] * arr[j]) % MOD;
}
}
for (int i = 1; i < n; i++)
{
prefixSum[i] = (prefixSum[i] + prefixSum[i - 1]) % MOD;
}
for (int i = 0; i < n; i++)
{
cout << prefixSum[i] << ' ';
}
return 0;
}
Subtask \(3\) (\(40\%\) số điểm): Không có rằng buộc gì thêm.
Tutorial
Subtask này sử dụng một kiến thức khá mới và đã xuất hiện trong những kì VOI gần đây (bài 3 VOI 2020): DP sum over subset
Note: trong phần solution này \(a \subseteq b\) nghĩa là tập bit \(1\) của a là subset của tập bit 1 của b trong hệ nhị phân hay nói cách khác \((a \& b) = a\) (ví dụ: \(0100 \subseteq 0111\)) tương tự với \(\subset\) thì là proper subset
Đầu tiên ta cần tính tổng \(a_i \cdot a_j\) sao cho \(i, j \subseteq U\)
Xét tập \(S = \left\{i \mid i \subseteq U \right\}\), \(sum\) là tổng \(a_i\) của tập \(S\). Vậy thì tổng \(a_i \cdot a_j\) (\(i, j \in S\)) của tập \(S\) sẽ là \(sum^2\).
Ta có mảng \(tot[mask]\) sẽ là tổng \(a_i \cdot a_j\) vừa tính ở trên.
Gọi \(ans[mask]\) là tổng \(a_i \cdot a_j\) sao cho \(i \mid j = mask\)
Nhận xét: \(tot[mask] - \sum{ans[submask]} (submask \subset mask) = ans[mask]\) vì trong mảng \(tot[mask]\) đang bao gồm các tổng \(a_i \cdot a_j\) sao cho \((i \& j) \subset mask\)
Đây chính là một hàm có thể tính bằng DP sum over subset. Cụ thể phần quy hoạch động có thể đọc thêm tại \(\href{https://codeforces.com/blog/entry/45223}{đây}\)
Độ phức tạp: \(\mathcal{O}\left(n \times \log_{2}(n)\right)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = (1 << 19);
const int MOD = 1000000007;
int n;
int arr[MAX_N];
int sum[MAX_N];
int dp[MAX_N];
int getBit(int num, int pos) {
return (num >> pos) & 1;
}
void add(int &a, int b) {
a += b;
if (a >= MOD) {
a -= MOD;
}
}
void sub(int &a, int b) {
a -= b;
if (a < 0) {
a += MOD;
}
}
void addSOS(int dp[], int n = 19) {
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < MAX_N; mask++) {
if (getBit(mask, i)) {
add(dp[mask], dp[mask ^ (1 << i)]);
}
}
}
}
void subSOS(int dp[], int n = 19) {
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < MAX_N; mask++) {
if (getBit(mask, i)) {
sub(dp[mask], dp[mask ^ (1 << i)]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum[i] = arr[i];
}
addSOS(sum);
for (int i = 0; i < MAX_N; i++) {
dp[i] = (long long)sum[i] * sum[i] % MOD;
}
subSOS(dp);
for (int i = 1; i < n; i++) {
add(dp[i], dp[i - 1]);
}
for (int i = 0; i < n; i++) {
cout << dp[i] << " ";
}
return 0;
}
Bình luận