Comments

• 
  

  0

  

  dex111222333444555  commented on Oct. 29, 2025, 11:11 a.m.

  Ý tưởng bài D

  Nhận xét: Nếu ta đặt a1 là số xuất phát, d2, d3, d4, ...., dk là khoảng cách giữa 2 số liền kề, ta sẽ có bất đẳng thức: a1 + d2 + d3 + ... + dk <= N Vậy, bài toán là đếm số cách xây dựng các số trong dãy a1, a2, ...., ak cũng là tương ứng với số cách xây dựng dãy a1, d2, d3, ...., dk. Bởi nếu có d2, d3, ...., dk thì các số a2 = a1 + d2, a3 = a1 + d2 + d3, ...., ak = a1 + d2 + d3 + .... + dk Vậy số cách xây dựng dãy được tính như nào ????? Ta thấy như sau: Giả sử ta đã biết bộ d2, d3, ...., dk, thì số cách để xây dựng ra a1 là: N - (d2 + d3 + .... + dk) Từ đó, số cách xây dựng được mô tả như sau: Bạn hãy xây dựng dãy d2, d3, ...., dk trước, và khi đó chỉ cần đếm số cách xây dựng ra a1 là xong Vậy tổng số cách là Tổng (N - (d2 + d3 + ..... + dk)) với mọi dãy d2, d3, ..., dk Tổng này có thể tách thành: Tổng ( N ) - Tổng (d2 + d3 + .... + dk) Tổng ( N ) được tính như sau: Cứ với một cách chọn ra d2, d3, ...., dk thì có 1 lần xuất hiện N. Do đó số cách chọn d2, d3, ..., dk là M^(K-1), nên Tổng 👎 = N * M^(K-1) Còn tổng (d2 + d3 + .... + dk) thì sao ? Ta thấy các số d2, d3, ....., dk được tự do thích chọn gì chọn. Do đó, nếu chỉ xét riêng số d2, thấy rằng d2 sẽ "đóng góp" vào trong tổng trên đó là: với mỗi d2 = 1, 2, 3, ...., M, thì d2 luôn xuất hiện với số lần bằng nhau và số lần đó = số cách chọn các d3, d4, ...., dk. Tức mỗi d2 xuất hiện M^(K - 2) lần, do đó tổng (d2) = (1 + 2 + .... + M) * M^(K - 2) = M * (M + 1) / 2 * M^(K - 2) Vì d2, d3, d4, ...., dk đóng vai trò giống nhau vì mỗi số đều được chọn một cách tự do, do đó tổng của tất cả các số sẽ bằng :
  M * (M + 1) / 2 * M^(K - 2) * (K - 1)
  Vậy kết quả chính là : N * M^(K - 1) - M * (M + 1) / 2 * M^(K - 2) * (K - 1)