Nhờ giải bải tập đánh giá độ phức tạp thuật toán

Nguyen_Ngoc_Hoai · March 7, 2021, 11:09am

[2 lost images]

tcm · January 10, 2017, 11:53am

Đây là bài tập phải không nhỉ ?

rogp10 · January 10, 2017, 1:48pm

Có lời giải
Thực ra cái này mới là dạng tính tổng, còn dạng truy hồi nữa mới chua.

thực ra nhị phân có thể đọc trực tiếp :v

tntxtnt · January 10, 2017, 1:39pm

ans = 0
for i1 = 1..n
    for i2 = (i1 + 1)..n
        for i3 = (i2 + 2)..n
            ...
                for iK = (i(k - 1) + (k - 1))..n
                    ans = ans + 1
print ans

1 <= n <= 2 x 10⁹
1 <= k <= 3 x 10⁵

hộc máu nhóe

Nguyen_Ngoc_Hoai · January 10, 2017, 3:23pm

Ai giải dùm với ạ mai thi rồi mà h này còn chưa làm đc mấy bài này

rogp10 · January 10, 2017, 4:27pm

Cuối cùng thì =))

Mấy tổng này lớp 8 đã tính được rồi. Thớt ôn lại cấp số cộng với cấp số nhân, hằng đẳng thức còn kịp.