Chia và trị: Đếm dãy số

#1

Các anh/chị cho em hỏi bài này với ạ, em xem qua lời giải thì thấy họ chỉ lấy 2^(n-1) là ra kết quả mà em không hiểu tại sao, em cũng có search gg thì không ra hoặc keyword tiếng anh của em chưa chuẩn nên mong anh/chị giải đáp giúp ạ.
Cho số nguyên dương n, bạn được phép sử dụng không giới hạn các số tự nhiên từ 1 tới n. Hỏi có bao nhiêu cách chọn ra 1 dãy có tổng các phần tử bằng n.

Input Format

Dòng duy nhất chứa số nguyên dương n

Constraints

1<=n<=10^12

Output Format

In ra đáp án của bài toán sau khi chia dư với 10^9 + 7

Sample Input 0

6

Sample Output 0

32

#2

ghi công thức đệ quy ra là thấy :V

n = 1 + (số cách chọn dãy có tổng là n-1)
n = 2 + (số cách chọn dãy có tổng là n-2)
n = 3 + (số cách chọn dãy có tổng là n-3)
…

n = n-2 + (số cách chọn dãy có tổng là 2)
n = n-1 + (số cách chọn dãy có tổng là 1)
n = n + (số cách chọn dãy có tổng là 0)

hay S(n) = \displaystyle\sum_{i=1}^{n}{S(n - i)}
thấy dãy này giống Fibonacci nè: dãy Fibo là tổng 2 số hạng trước nó: 0 1 1 2 3 5 8…, còn dãy này là tổng tất cả các số hạng trước nó: 1 1 2 4 8 16… dễ dàng thấy nó có dạng 2^{n-1} thôi :V :V

\begin{aligned} S(n) &= S(n-1) + \underbrace{S(n-2) + S(n-3) + ... + S(1) + S(0)}_{S(n-1)} \\ &= S(n-1) + S(n-1) \\ &= 2S(n-1) \\ &= 2 * \underbrace{S(n-1)}_{2*S(n-2)} \\ &= 2^2 * \underbrace{S(n-2)}_{2*S(n-3)} \\ &= 2^3 * \underbrace{S(n-3)}_{2*S(n-4)} \\ &= ... \\ &= 2^{n-1}*S(1) \\ &= 2^{n-1} \end{aligned}
6 Likes
#3

Bạn dùng phương pháp sau để dễ hình dung (click vào để xem hình):

3 Likes
#4

a cho e hỏi là nếu vậy có nhiều cách trùng nhau theo công thức đệ quy đó thì sao ạ

#5

thì chắc chuyển về bài toán như đếm số cách thối tiền ấy, mà giá trị các đồng xu từ 1 tới n luôn chứ ko phải 1, 2, 5 gì nữa :V

chạy thử thì thấy ra dãy này https://oeis.org/A000041 ko biết đúng ko
thấy định nghĩa chắc là đúng: https://en.wikipedia.org/wiki/Partition_(number_theory)

giải bài coin change này https://leetcode.com/problems/coin-change-ii/ rồi input test case là ví dụ 5 [1,2,3,4,5] hay 6 [1,2,3,4,5,6] là thấy nó ra đúng số thôi :V :V

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?