Hướng dẫn giải của Bé làm toán (đề Hòa Bình 2021)


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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

Dãy vô hạn gồm 1 số 1, 2 số 2, 3 số 3, ... Cần tính tổng các số ở vị trí từ ~A~ đến ~B~ (~B \le 10^9~), lấy dư ~10^9+7~. Đặt ~S(m)~ là tổng ~m~ số đầu tiên thì đáp án là ~S(B) - S(A-1)~.

Sub 1: Tạo dãy tường minh — ~O(B)~, dùng khi ~B \le 10^5~

Sinh dãy đến vị trí ~B~ rồi cộng từ vị trí ~A~ đến ~B~. Nếu chỉ nộp sub này: đúng 27/30 test (3 test lớn không chạy kịp).

Sub 2: Cộng theo nhóm — ~O(\sqrt{B})~

Nhóm thứ ~k~ gồm ~k~ số ~k~, nên đến vị trí ~B~ chỉ có khoảng ~\sqrt{2B}~ nhóm (tối đa khoảng 45000). Với mỗi nhóm cộng ~\min(k, \text{số vị trí còn lại}) \cdot k~, lấy dư sau mỗi phép nhân. Đáp án ~(S(B) - S(A-1)) \bmod (10^9+7)~, nhớ cộng thêm ~10^9+7~ nếu âm. Nộp riêng sub này đúng 30/30 test.

Chương trình hoàn chỉnh

Hàm ~main~ đọc ~A, B~; nếu ~B \le 10^5~ 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 30/30 test.

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

const long long MOD = 1000000007;
long long A, B;

// S(m) = tổng m số đầu tiên của dãy 1,2,2,3,3,3,... theo cách tính từng nhóm (không mod trong phép nhân lớn)
long long prefixSum(long long m) {
    long long res = 0, k = 1;
    while (m > 0) {                      // nhóm k gồm k số k; số lượng chạy theo căn m
        long long take = min(k, m);
        res = (res + (take % MOD) * (k % MOD)) % MOD;
        m -= take;
        k++;
    }
    return res;
}

// Sub 1: tạo dãy tường minh đến vị trí B rồi cộng từ A đến B, O(B), dùng khi B <= 10^5
void sub1() {
    vector<int> v;
    v.push_back(0);                      // chỉ số từ 1
    for (int k = 1; (long long)v.size() <= B; k++)
        for (int j = 0; j < k && (long long)v.size() <= B; j++) v.push_back(k);
    long long s = 0;
    for (long long i = A; i <= B; i++) s += v[i];
    cout << s % MOD << "\n";
}

// Sub 2: tổng tiền tố S(B) - S(A-1), mỗi S duyệt các nhóm, chỉ ~sqrt(2B) nhóm: O(sqrt(B))
void sub2() {
    long long ans = ((prefixSum(B) - prefixSum(A - 1)) % MOD + MOD) % MOD;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> A >> B;
    if (B <= 100000) sub1();
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.