Tổng (THPT16 – Bài 4)

Nguồn: Đề thi HSG Tin học THPT (Bài 4) Độ khó: Trung bình Toán học Tìm quy luật Cấp số cộng Modulo

Đề bài

Bài 4: (3 điểm).

Long, một sinh viên đang học ngành khoa học máy tính tại Đại học Công Nghệ, Đại học Quốc gia Hà Nội được mọi người biết đến với khả năng toán học vô cùng xuất sắc. Hôm nay, giáo viên Toán của Long đã đố anh ta giải một bài toán rất khó khăn như sau: Xét hai tập số vô hạn là tập số nguyên dương lẻ $(1, 3, 5, 7, \dots)$ và tập số nguyên dương chẵn $(2, 4, 6, 8, \dots)$. Ở giai đoạn đầu tiên, giáo viên viết lên bảng 1 số đầu tiên từ tập thứ nhất. Ở giai đoạn thứ 2, giáo viên viết lên bảng 2 số đầu tiên từ tập thứ hai. Ở giai đoạn thứ 3, giáo viên viết lên bảng 4 số tiếp theo ở tập thứ nhất. Ở giai đoạn thứ 4, giáo viên viết lên bảng 8 số tiếp theo ở tập thứ hai và cứ như thế. Nói cách khác, ở mỗi giai đoạn, bắt đầu từ lần thứ hai, anh ta viết số lượng số nhiều gấp đôi số lượng số đã viết ở lần trước và cũng thay đổi tập hợp so với lần trước. Ví dụ: 10 số đầu tiên được viết lên bảng là 1, 2, 4, 3, 5, 7, 9, 6, 8, 10. Các số trên bảng được đánh số từ 1. Giáo viên sẽ cho Long 2 số nguyên dương $L$, $R$ $(L \le R)$. Tìm tổng các số nguyên được đánh số từ $L$ đến $R$ được viết trên bảng.

Dữ liệu: vào từ file BAI4.INP gồm 2 số nguyên dương $L$ và $R$ $(L \le R \le 10^{18})$.

Kết quả: ghi ra file BAI4.OUT là kết quả của bài toán. Vì kết quả có thể rất lớn nên chỉ cần tính tổng các số theo modulo $10^9+7$ (phép lấy phần dư).

Ghi chú: trên hệ thống chấm online (NTUCoder) thì các bạn đọc dữ liệu từ bàn phím và in kết quả ra màn hình (stdin/stdout) nhé.

Ví dụ 1 – BAI4.INP

3 10

BAI4.OUT

52

Ví dụ 2 – BAI4.INP

1000 5000

BAI4.OUT

12058627

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước tiên mình giải thích test đầu tiên, vì sao input 3 10 lại ra 52. Dãy theo quy tắc đề bài như sau: 1 số lẻ, rồi 2 số chẵn, rồi 4 số lẻ, rồi 8 số chẵn, rồi 16 số lẻ, 32 số chẵn... cứ thế. Vậy phần đầu tiên của dãy sẽ là (cam là lẻ, xanh là chẵn):

1 | 2 4 | 3 5 7 9 | 6 8 10 12 14 16 18 20 | 11 13 15 ...

Tính đầu dãy là vị trí 1, thì từ vị trí $L = 3$ đến vị trí $R = 10$ sẽ là các số: $4, 3, 5, 7, 9, 6, 8, 10$, tổng của tụi nó là $4 + 3 + 5 + 7 + 9 + 6 + 8 + 10 = 52$ đó các bạn.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Làm theo đề, viết từng số – O(R) · chỉ chạy được R nhỏCách 2Chia nhóm 2^k + cấp số cộng – O(log R) · 100%

Cách 1Làm theo đề, viết từng số lên bảng – O(R)

Cách ai cũng nghĩ ra đầu tiên: mô phỏng đúng như thầy giáo viết bảng. Ta giữ 2 biến odd (số lẻ tiếp theo, bắt đầu 1) và even (số chẵn tiếp theo, bắt đầu 2), biến cnt là số lượng số của giai đoạn hiện tại (1, 2, 4, 8...). Giai đoạn thứ $k$ (đếm từ 0) mà $k$ chẵn thì lấy số lẻ, $k$ lẻ thì lấy số chẵn. Mỗi lần viết 1 số thì tăng pos (vị trí trên bảng), nếu pos đã nằm trong đoạn $[L, R]$ thì cộng vào tổng (nhớ lấy modulo). Viết tới vị trí $R$ thì dừng.

Cách này dùng để hiểu đề và làm code vét cạn đối chiếu thì rất tốt, nhưng $R$ lên tới $10^{18}$ thì không có cách nào chạy kịp đâu nha.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

int main(){
    long long l, r, m = 1000000007;
    cin >> l >> r;
    long long odd = 1, even = 2, cnt = 1, pos = 0, sum = 0;
    for(int k = 0; pos < r; ++k){
        for(long long j = 1; j <= cnt && pos < r; ++j){
            long long v;
            if(k % 2 == 0){
                v = odd; odd += 2;
            }
            else{
                v = even; even += 2;
            }
            pos++;
            if(pos >= l) sum = (sum + v) % m;
        }
        cnt *= 2;
    }
    cout << sum;
    return 0;
}

l, r = map(int, input().split())
m = 10**9 + 7
odd, even, cnt, pos, s = 1, 2, 1, 0, 0
k = 0
while pos < r:
    j = 1
    while j <= cnt and pos < r:
        if k % 2 == 0:
            v = odd
            odd += 2
        else:
            v = even
            even += 2
        pos += 1
        if pos >= l:
            s = (s + v) % m
        j += 1
    cnt *= 2
    k += 1
print(s)

C++▶ Chạy tay từng dòng codeCách 1: viết lần lượt từng số lên bảng, cộng các số ở vị trí từ L đến R.

Dữ liệu vào (stdin) – sửa thoải mái3 10

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long l, r, m = 1000000007;

6 cin >> l >> r;

7 long long odd = 1, even = 2, cnt = 1, pos = 0, sum = 0;

8 for(int k = 0; pos < r; ++k){

9 for(long long j = 1; j <= cnt && pos < r; ++j){

10 long long v;

11 if(k % 2 == 0){

12 v = odd; odd += 2;

13 }

14 else{

15 v = even; even += 2;

16 }

17 pos++;

18 if(pos >= l) sum = (sum + v) % m;

19 }

20 cnt *= 2;

21 }

22 cout << sum;

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ vài biến đơn → $O(1)$.
• Thời gian: phải viết đủ $R$ số lên bảng → $O(R)$.

Không gian$O(1)$

Thời gian$O(R)$

Không thể chạy với R = 10^18

Mình đo thử: với $R = 10^9$ bản C++ đã mất khoảng 4 giây CPU rồi, mà $R$ tối đa tới $10^{18}$ (gấp $10^9$ lần nữa) thì chạy tới... tết năm sau 😅. Nên mình cần một cách không phải đi qua từng số.

Cách 2Chia dãy thành các nhóm 2^k, tính tổng bằng cấp số cộng – O(log R)

Bước 1: dãy chỉ có khoảng 60 nhóm

Tối đa $R$ có thể lên đến $10^{18}$. Nhưng theo quy tắc của bài thì số lượng số mỗi giai đoạn cứ liên tục gấp đôi lên: 1 số lẻ, 2 số chẵn, 4 số lẻ, 8 số chẵn, 16 số lẻ, 32 số chẵn... Các bạn sẽ thấy đó chính là các giá trị $2^k$ với $k$ bắt đầu từ 0: $2^0 = 1,\ 2^1 = 2,\ 2^2 = 4,\ 2^3 = 8,\ 2^4 = 16,\ 2^5 = 32 \dots$

Tổng các lũy thừa của 2

$2^0 + 2^1 + 2^2 + \dots + 2^k = 2^{k+1} - 1$

Muốn phủ tới vị trí $R = 10^{18}$ thì cần $2^{k+1} - 1 \approx 10^{18}$. Trừ 1 quá nhỏ nên coi như không có đi ha, lúc này còn $2^{k+1} = 10^{18} \Leftrightarrow 2 \cdot 2^k = 10^{18} \Leftrightarrow 2^k = 5 \cdot 10^{17}$, tính ra $k = \log_2(5 \cdot 10^{17}) \approx 59$. Vậy cả dãy tới vị trí $10^{18}$ chỉ gồm khoảng 60 nhóm thôi! Mình cho luôn 60 nhóm cho thoải mái.

Với mỗi nhóm, ta xác định được phạm vi số thứ tự (vị trí trên bảng) và miền giá trị (các số được viết, bước nhảy +2 vì chỉ lấy toàn lẻ hoặc toàn chẵn):

Nhóm i	Loại	startOder	finishOder	startValue	finishValue
1	1 số lẻ	1	1	1	1
2	2 số chẵn	2	3	2	4
3	4 số lẻ	4	7	3	9
4	8 số chẵn	8	15	6	20
5	16 số lẻ	16	31	11	41
6	32 số chẵn	32	63	22	84
...	...	...	...	...	...

Mình cho mảng bắt đầu từ 1 nên mảng có 61 phần tử để dùng index từ 1 đến 60; index tính từ 1 thì nó trùng với quy luật "lẻ trước rồi tới chẵn" cho dễ: i lẻ là nhóm số lẻ, i chẵn là nhóm số chẵn. Mỗi phần tử là một struct có 4 thông tin:

• startOder: số thứ tự bắt đầu của nhóm, finishOder: số thứ tự kết thúc.
• startValue: giá trị phần tử bắt đầu, finishValue: giá trị phần tử kết thúc.

Ví dụ với a[3] (4 số lẻ): số thứ tự từ 4 đến 7, miền giá trị từ 3 đến 9, tức là startOder = 4, finishOder = 7, startValue = 3, finishValue = 9. Nhìn một chút là ra quy luật để cài:

Công thức tạo mảng a

• Với $x = 2^{i-1}$: startOder = x, finishOder = 2x - 1.
• Nhóm $i \ge 3$ nối tiếp nhóm cùng loại $i - 2$ (lẻ nối lẻ, chẵn nối chẵn): startValue = a[i-2].finishValue + 2.
• Nhóm có $x$ số, bước nhảy 2: finishValue = startValue + (x - 1) * 2 (trong code thầy viết là (startOder - 1) * 2 + startValue, vì startOder = x).

Bước 2: tổng các số từ x đến y, bước nhảy 2

Mình viết hàm GetSumXTOY(x, y) tính tổng các số từ $x$ đến $y$ với bước nhảy +2. Ví dụ GetSumXTOY(4, 10) là $4 + 6 + 8 + 10$, còn GetSumXTOY(3, 7) là $3 + 5 + 7$. Đây là tổng cấp số cộng:

Tổng cấp số cộng

$b_1 + b_2 + \dots + b_n = \dfrac{(b_1 + b_n) \cdot n}{2}$, với số phần tử $n = \dfrac{y - x}{2} + 1$.

Để ý $x$, $y$ luôn cùng chẵn hoặc cùng lẻ, nên $x + y$ chắc chắn là số chẵn ⇒ mình lấy $z = (x + y) / 2$ chia luôn trước để giảm độ lớn, chứ không phải nhân cho $n$ rồi mới chia 2. Sau đó lấy $z \cdot n$, và vì kết quả có thể rất lớn nên áp dụng công thức modulo phép nhân:

Modulo phép nhân

$(a \cdot b) \bmod c = \big((a \bmod c) \cdot (b \bmod c)\big) \bmod c$

Vì sao phải chia 2 trước?

Nếu tính $(x + y) \cdot n$ rồi mới chia 2, thì $x + y$ cỡ $3 \cdot 10^{18}$ nhân $n$ cỡ $5 \cdot 10^{17}$ là tràn long long ngay. Còn nếu lấy modulo trước rồi mới chia 2 thì phép chia sai (chia trong modulo không làm vậy được). Chia 2 trước (chia hết, không sai số), rồi mỗi thừa số lấy % m (đều nhỏ hơn $10^9+7$) thì tích nhỏ hơn $10^{18}$, an toàn.

Bước 3: ghép đoạn [L, R]

Có mảng a rồi thì việc tính tổng các giá trị trong đoạn $L$ đến $R$ đơn giản như sau. Ví dụ $L = 3$, $R = 10$: $L = 3$ thuộc về a[2], $R = 10$ thuộc về a[4] (gọi là idxStart và idxFinish). Thì:

• sum2: giữa 2 và 4 chỉ có a[3], tính tổng toàn bộ nhóm này bằng GetSumXTOY(a[3].startValue, a[3].finishValue) = $3 + 5 + 7 + 9 = 24$.
• sum1: xác định giá trị tại vị trí $L$ trong a[2]: (L - startOder) * 2 + startValue = $(3 - 2) \cdot 2 + 2 = 4$, rồi tính tổng từ đó đến cuối nhóm (finishValue) = $4$.
• sum3: xác định giá trị tại vị trí $R$ trong a[4]: $(10 - 8) \cdot 2 + 6 = 10$, tính tổng từ đầu nhóm đến đó = $6 + 8 + 10 = 24$.

Kết quả $4 + 24 + 24 = 52$ 🎉. Đó là tình huống $L$, $R$ khác nhóm. Còn nếu idxStart == idxFinish (cùng một nhóm) thì ta xác định giá trị tại vị trí $L$ là x1, giá trị tại $R$ là x1 + (R - L) * 2, rồi gọi GetSumXTOY một lần là xong.

Minh hoạ chia nhóm và ghép tổng

Em nhập $L$, $R$ (nhỏ thôi để vẽ được) rồi bấm Tiếp để xem từng bước nhé:

L R

Ví dụ nhanh:

Source code giải quyết theo tư tưởng đã trình bày trên các bạn xem để được hiểu rõ hơn:

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

long long m = 1000000007;

long long GetSumXTOY(long long x, long long y){
    long long n = (y - x) / 2 + 1;
    long long z = (x + y) / 2;
    return ((z % m) * (n % m)) % m;
}

struct Data{
    long long startOder, finishOder, startValue, finishValue;
};

long long solve(long long l, long long r){
    Data a[61];
    long long x = 1;
    a[1].startValue = 1; a[1].finishValue = 1;
    a[2].startValue = 2; a[2].finishValue = 4;
    for(int i = 1; i <= 60; ++i){
        a[i].startOder = x;
        a[i].finishOder = x * 2 - 1;
        if(i >= 3){
            a[i].startValue = a[i - 2].finishValue + 2;
            a[i].finishValue = (a[i].startOder - 1) * 2 + a[i].startValue;
        }
        x *= 2;
    }
    int idxStart, idxFinish;
    for(int i = 1; i <= 60; ++i){
        if(l >= a[i].startOder && l <= a[i].finishOder){
            idxStart = i;
        }
        if(r >= a[i].startOder && r <= a[i].finishOder){
            idxFinish = i;
            break;
        }
    }
    long long sum1 = 0, sum2 = 0, sum3 = 0;
    for(int i = idxStart + 1; i < idxFinish; ++i){
        sum2 += GetSumXTOY(a[i].startValue, a[i].finishValue);
        sum2 %= m;
    }
    if(idxStart != idxFinish){
        sum1 = GetSumXTOY((l - a[idxStart].startOder) * 2 + a[idxStart].startValue, a[idxStart].finishValue);
        sum3 = GetSumXTOY(a[idxFinish].startValue, (r - a[idxFinish].startOder) * 2 + a[idxFinish].startValue);
        return (sum1 + sum2 + sum3) % m;
    }
    // idxStart == idxFinish
    long long x1 = (l - a[idxStart].startOder) * 2 + a[idxStart].startValue;
    sum1 = GetSumXTOY(x1, (r - l) * 2 + x1);
    return (sum1 + sum2) % m;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    long long l, r;
    cin >> l >> r;
    cout << solve(l, r);
    return 0;
}

m = 10**9 + 7

def GetSumXTOY(x, y):
    n = (y - x) // 2 + 1
    z = (x + y) // 2
    return (z % m) * (n % m) % m

class Data:
    def __init__(self):
        self.startOder = 0
        self.finishOder = 0
        self.startValue = 0
        self.finishValue = 0

def solve(l, r):
    a = [Data() for _ in range(61)]
    x = 1
    a[1].startValue = 1
    a[1].finishValue = 1
    a[2].startValue = 2
    a[2].finishValue = 4
    for i in range(1, 61):
        a[i].startOder = x
        a[i].finishOder = x * 2 - 1
        if i >= 3:
            a[i].startValue = a[i - 2].finishValue + 2
            a[i].finishValue = (a[i].startOder - 1) * 2 + a[i].startValue
        x *= 2
    idxStart = idxFinish = -1
    for i in range(1, 61):
        if l >= a[i].startOder and l <= a[i].finishOder:
            idxStart = i
        if r >= a[i].startOder and r <= a[i].finishOder:
            idxFinish = i
            break
    sum1 = sum2 = sum3 = 0
    for i in range(idxStart + 1, idxFinish):
        sum2 = (sum2 + GetSumXTOY(a[i].startValue, a[i].finishValue)) % m
    if idxStart != idxFinish:
        sum1 = GetSumXTOY((l - a[idxStart].startOder) * 2 + a[idxStart].startValue, a[idxStart].finishValue)
        sum3 = GetSumXTOY(a[idxFinish].startValue, (r - a[idxFinish].startOder) * 2 + a[idxFinish].startValue)
        return (sum1 + sum2 + sum3) % m
    else:
        x1 = (l - a[idxStart].startOder) * 2 + a[idxStart].startValue
        sum1 = GetSumXTOY(x1, (r - l) * 2 + x1)
        return (sum1 + sum2) % m

l, r = map(int, input().split())
print(solve(l, r))

Khung chạy tay bên dưới chạy được cả với $R = 10^{18}$ luôn nha (mình dùng số nguyên lớn để mô phỏng đúng long long). Bảng "Dữ liệu" chỉ hiện các nhóm đầu và các nhóm quanh $L$, $R$ cho gọn.

C++▶ Chạy tay từng dòng codeCách 2: tạo 60 nhóm, tìm nhóm chứa L, R rồi cộng sum1 + sum2 + sum3 bằng công thức cấp số cộng.

Dữ liệu vào (stdin) – sửa thoải mái3 10

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long m = 1000000007;

5

6long long GetSumXTOY(long long x, long long y){

7 long long n = (y - x) / 2 + 1;

8 long long z = (x + y) / 2;

9 return ((z % m) * (n % m)) % m;

10}

11

12struct Data{

13 long long startOder, finishOder, startValue, finishValue;

14};

15

16long long solve(long long l, long long r){

17 Data a[61];

18 long long x = 1;

19 a[1].startValue = 1; a[1].finishValue = 1;

20 a[2].startValue = 2; a[2].finishValue = 4;

21 for(int i = 1; i <= 60; ++i){

22 a[i].startOder = x;

23 a[i].finishOder = x * 2 - 1;

24 if(i >= 3){

25 a[i].startValue = a[i - 2].finishValue + 2;

26 a[i].finishValue = (a[i].startOder - 1) * 2 + a[i].startValue;

27 }

28 x *= 2;

29 }

30 int idxStart, idxFinish;

31 for(int i = 1; i <= 60; ++i){

32 if(l >= a[i].startOder && l <= a[i].finishOder){

33 idxStart = i;

34 }

35 if(r >= a[i].startOder && r <= a[i].finishOder){

36 idxFinish = i;

37 break;

38 }

39 }

40 long long sum1 = 0, sum2 = 0, sum3 = 0;

41 for(int i = idxStart + 1; i < idxFinish; ++i){

42 sum2 += GetSumXTOY(a[i].startValue, a[i].finishValue);

43 sum2 %= m;

44 }

45 if(idxStart != idxFinish){

46 sum1 = GetSumXTOY((l - a[idxStart].startOder) * 2 + a[idxStart].startValue, a[idxStart].finishValue);

47 sum3 = GetSumXTOY(a[idxFinish].startValue, (r - a[idxFinish].startOder) * 2 + a[idxFinish].startValue);

48 return (sum1 + sum2 + sum3) % m;

49 }

50 // idxStart == idxFinish

51 long long x1 = (l - a[idxStart].startOder) * 2 + a[idxStart].startValue;

52 sum1 = GetSumXTOY(x1, (r - l) * 2 + x1);

53 return (sum1 + sum2) % m;

54}

55

56int main(){

57 ios::sync_with_stdio(0); cin.tie(0);

58 long long l, r;

59 cin >> l >> r;

60 cout << solve(l, r);

61 return 0;

62}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng a chỉ 61 phần tử cố định → $O(1)$.
• Thời gian: các vòng lặp đều chạy tối đa 60 lần (số nhóm cỡ $\log_2 R$), mỗi lần gọi GetSumXTOY là $O(1)$ → $O(\log R)$, mà $\log R \le 60$ nên gần như có thể nói là $O(1)$ (độ phức tạp hằng số) luôn.

Không gian$O(1)$

Thời gian$O(\log R) \approx O(60)$

Có tràn long long không?

Nhóm 60 có finishValue khoảng $1.54 \cdot 10^{18}$, cộng startValue trong GetSumXTOY cũng chỉ khoảng $1.9 \cdot 10^{18}$, vẫn nhỏ hơn giới hạn long long ($\approx 9.2 \cdot 10^{18}$). Còn phép nhân thì mỗi thừa số đã % m nên tích dưới $10^{18}$. Yên tâm nha 😎.

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với 1338 bộ test (ngẫu nhiên với $R$ nhỏ lẫn $R$ tới $10^{18}$, cộng các biên $2^k - 1$, $2^k$, $2^k + 1$), so với một hàm tính tổng chính xác bằng số nguyên lớn – khớp hết; cả 2 ví dụ của đề đều ra đúng. Với $L = 1$, $R = 10^{18}$ bản C++ chạy tức thì (khoảng 0.01 giây). Code cách 1 cũng được so khớp với cách 2 trên 300 bộ test có $R \le 3000$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇