Hướng dẫn cho LQDOJ Cup 2023 - Final Round - Password

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

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: kitsune

Tóm tắt đề bài

Cho hai dãy số \(a_1..a_n\) (hàng trên) và \(b_1..b_n\) (hàng dưới). Ở mỗi bước, ta tính

\[S_t = \sum_{i=1}^{n} a_i \cdot b_{(i+t-1 \bmod n)+1}\]

với \(t=0,1,2,\ldots\) (mỗi lần tăng \(t\) tương ứng xoay dãy \(b\) sang trái 1 ô). Mật khẩu là tổng của \(k\) giá trị đầu tiên \(S_0 + S_1 + \cdots + S_{k-1}\), lấy modulo \(10^9+7\).

Phân tích

\(n \le 10^5\) nhưng \(k \le 10^9\) nên không thể mô phỏng \(k\) lần xoay.
Nhận xét quan trọng:
- Dãy \(S_t\) có chu kỳ \(n\) vì xoay \(n\) lần thì \(b\) trở về ban đầu.
- Vì vậy, tổng \(k\) phần tử đầu tiên có thể tách thành:
  - Nhiều chu kỳ đầy đủ (mỗi chu kỳ dài \(n\)),
  - Và một đoạn dư dài \(k \bmod n\).

Tổng trên một chu kỳ

Xét tổng của một chu kỳ:

\[\sum_{t=0}^{n-1} S_t = \sum_{t=0}^{n-1} \sum_{i=1}^{n} a_i \cdot b_{(i+t-1 \bmod n)+1}\]

Với mỗi \(i\) cố định, khi \(t\) chạy \(0..n-1\) thì chỉ số của \(b\) chạy qua mọi vị trí đúng 1 lần, nên:

\[\sum_{t=0}^{n-1} a_i \cdot b_{(i+t-1 \bmod n)+1} = a_i \cdot \sum_{j=1}^{n} b_j\]

Suy ra:

\[\sum_{t=0}^{n-1} S_t = \left(\sum_{i=1}^{n} a_i\right)\left(\sum_{j=1}^{n} b_j\right)\]

Đây là “khối” đóng góp của mỗi chu kỳ đầy đủ.

Phần dư (không đủ \(n\) bước)

Cần tính:

\[\sum_{t=0}^{r-1} S_t \quad \text{với } r = k \bmod n\]

Viết lại theo góc nhìn “mỗi \(a_i\) nhân với \(r\) phần tử liên tiếp của \(b\) trên vòng tròn”:

\[\sum_{t=0}^{r-1} S_t = \sum_{i=1}^{n} a_i \cdot \left(\sum_{t=0}^{r-1} b_{(i+t-1 \bmod n)+1}\right)\]

Tức là với mỗi \(i\), ta cần tổng \(r\) phần tử liên tiếp của \(b\) bắt đầu từ vị trí \(i\) (theo vòng tròn). Bài toán trở thành tính nhanh tổng đoạn trên mảng vòng tròn, dùng prefix sum trên mảng \(b\) được “nhân đôi”.

Hướng giải quyết

Ý tưởng chính

Tính:
- \(A = \sum a_i \bmod M\)
- \(B = \sum b_i \bmod M\), với \(M = 10^9+7\)
Số chu kỳ đầy đủ: \(q = \left\lfloor \frac{k}{n} \right\rfloor\), phần dư: \(r = k \bmod n\)
Đóng góp từ các chu kỳ đầy đủ:

\[ans = q \cdot A \cdot B \bmod M\]

Để tính phần dư dài \(r\):
- Tạo prefix sum cho mảng \(b\) dài \(2n\) bằng cách nối \(b\) với chính nó: \(b_1..b_n,b_1..b_n\).
- Khi đó tổng \(r\) phần tử liên tiếp bắt đầu tại \(i\) (trong \(1..n\)) là:

\[\text{sumB}(i) = psum[i+r-1] - psum[i-1] \pmod M\]

- Cộng vào đáp án:

\[ans = \sum_{i=1}^{n} a_i \cdot \text{sumB}(i) \bmod M\]

Liên hệ với code AC đã cho

Code tính sum = sum(a[i]).
psum[n] chính là \(\sum b_i\).
Dòng:

answer = 1LL * (k / n) * sum % MOD * psum[n] % MOD;

tương ứng phần chu kỳ đầy đủ \(q \cdot A \cdot B\).

Sau đó k %= n (tức \(r\)).
Mảng psum được xây cho tới 2*n để lấy tổng đoạn vòng tròn.
Vòng lặp cuối cộng \(\sum a_i \cdot (\text{tổng } r \text{ phần tử b liên tiếp})\).

Lưu ý / bẫy thường gặp

Nếu \(r=0\) thì phần dư bằng \(0\), vòng lặp vẫn chạy nhưng cần đảm bảo chỉ số hợp lệ. Trong code, với \(k=0\) sau k%=n, biểu thức i + k - 1 sẽ thành i-1 gây sai. Tuy nhiên đề bài có \(k \ge 1\), nhưng vẫn có thể xảy ra \(r=0\) khi \(k\) chia hết cho \(n\).
- Code AC này vẫn chạy vòng lặp, và khi \(k=0\) thì sẽ truy cập psum[i-1] - psum[i-1] nếu chỉnh đúng chỉ số; nhưng hiện tại psum[i + k - 1] = psum[i-1] hợp lệ, nên đoạn tổng bằng \(0\) và không lỗi. (Vì i-1 trong \([0..n-1]\).)
Phải luôn cộng thêm +MOD trước khi %MOD để tránh âm khi trừ prefix sum.

Độ phức tạp

Thời gian: \(O(n)\) (tính tổng, xây prefix sum tới \(2n\), và duyệt \(n\) phần tử)
Bộ nhớ: \(O(n)\)

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
const int MOD = 1000000007;

int n, k;
int a[MAX_N], b[MAX_N];
int psum[2 * MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("PASSWORD.inp", "r", stdin);
    freopen("PASSWORD.out", "w", stdout);

    cin >> n >> k;

    int sumA = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sumA = (sumA + a[i]) % MOD;
    }

    // Prefix sum cho b[1..n]
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        psum[i] = (psum[i - 1] + b[i]) % MOD;
    }

    // Phần chu kỳ đầy đủ
    long long q = k / n;
    int r = k % n;

    long long ans = q % MOD;
    ans = ans * sumA % MOD;
    ans = ans * psum[n] % MOD; // psum[n] = sumB

    // Nhân đôi mảng b để lấy tổng đoạn trên vòng tròn
    for (int i = n + 1; i <= 2 * n; i++) {
        psum[i] = (psum[i - 1] + b[i - n]) % MOD;
    }

    // Cộng phần dư: với mỗi i, lấy r phần tử b liên tiếp bắt đầu từ i
    for (int i = 1; i <= n; i++) {
        int L = i;
        int R = i + r - 1;
        int sumSegment = (psum[R] - psum[L - 1] + MOD) % MOD;
        ans = (ans + 1LL * a[i] * sumSegment) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

Subtask \(1\)

Tutorial

Làm như những gì đề yêu cầu.

Độ phức tạp: \(O(n \times k)\).

Solution

C++

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 1e5 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "PASSWORD";

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    deque<int> b(n);
    for (auto& x : b) {
        cin >> x;
    }

    int ans = 0;
    while (k--) {
        rep (i, 0, n - 1) {
            (ans += a[i] * (ll)b[i] % mod) %= mod;
        }

        b.push_back(b.front());
        b.pop_front();
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask \(2\)

Tutorial

Nhận xét rằng khi xoay dãy phía dưới đủ \(n\) lần thì thì nó trở về như cũ. Vậy ta có thể:

Tính tổng cho \(n\) lần xoay rồi nhân kết quả với \(\left \lfloor \frac{k}{n} \right \rfloor\).
Tính riêng cho số lần xoay còn lại như subtask 1.

Độ phức tạp: \(O(n ^ 2)\).

Solution

C++

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 1e5 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "PASSWORD";

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    deque<int> b(n);
    for (auto& x : b) {
        cin >> x;
    }

    int tot = 0;
    rep (_, 1, n) {
        rep (i, 0, n - 1) {
            (tot += a[i] * (ll)b[i] % mod) %= mod;
        }

        b.push_back(b.front());
        b.pop_front();
    }

    int ans = (k / n) * (ll)tot % mod;
    k %= n;

    rep (_, 1, k) {
        rep (i, 0, n - 1) {
            (ans += a[i] * (ll)b[i] % mod) %= mod;
        }

        b.push_back(b.front());
        b.pop_front();
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask \(3\)

Tutorial

Ta có thể cải tiến bằng cách sử dụng tổng tiền tố cho cả hai lần tính của subtask 2.

Độ phức tạp: \(O(n)\).

Solution

C++

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 1e5 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "PASSWORD";

int a[siz], b[siz];
int psum[2 * siz];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    int n, k;
    cin >> n >> k;

    int sum = 0;
    rep (i, 1, n) {
        cin >> a[i];

        (sum += a[i]) %= mod;
    }

    rep (i, 1, n) {
        cin >> b[i];

        psum[i] = (psum[i - 1] + b[i]) % mod;
    }

    int ans = (k / n) * (ll)sum % mod * psum[n] % mod;
    k %= n;

    rep (i, n + 1, 2 * n) {
        psum[i] = (psum[i - 1] + b[i - n]) % mod;
    }

    rep (i, 1, n) {
        (ans += a[i] * (ll)(psum[i + k - 1] - psum[i - 1] + mod) % mod) %= mod;
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.