CEOI 2018 - Day 2

Dãy Fibonacci trong bài này được định nghĩa như sau:

• \(F_1=1\).
• \(F_2=2\).
• \(F_n=F_{n-1}+F_{n-2}\) với \(n\ge3\).

Các số đầu tiên là \(1,2,3,5,8,13,21,\ldots\). Với số nguyên dương \(p\), gọi \(X(p)\) là số cách biểu diễn \(p\) thành tổng của các số Fibonacci khác nhau. Hai cách biểu diễn được xem là khác nhau nếu tồn tại một số Fibonacci xuất hiện trong đúng một cách.

Cho dãy số nguyên dương \(a_1,a_2,\ldots,a_n\). Với mỗi tiền tố không rỗng \(a_1,a_2,\ldots,a_k\), đặt \(p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}\). Hãy tính \(X(p_k)\) modulo \(10^9+7\) với mọi \(k=1,2,\ldots,n\).

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le100000\)).

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(1\le a_i\le10^9\)).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(k\) chứa \(X(p_k)\) modulo \(10^9+7\).

Ví dụ

4
4 1 1 5

2
2
1
2

Giải thích

Các giá trị lần lượt là \(p_1=F_4=5\), \(p_2=F_4+F_1=6\), \(p_3=F_4+F_1+F_1=7\) và \(p_4=F_4+F_1+F_1+F_5=15\).

Số \(5\) có hai cách biểu diễn: \(F_2+F_3\) và \(F_4\). Số \(6\) có hai cách: \(F_1+F_4\) và \(F_1+F_2+F_3\). Số \(7\) chỉ có cách \(F_2+F_4\). Số \(15\) có hai cách: \(F_2+F_6\) và \(F_2+F_4+F_5\).

Phân nhóm

1. \(5\) điểm: \(n,a_i\le15\).
2. \(20\) điểm: \(n,a_i\le100\).
3. \(15\) điểm: \(n\le100\) và các \(a_i\) là các số chính phương đôi một khác nhau.
4. \(10\) điểm: \(n\le100\).
5. \(15\) điểm: Các \(a_i\) là các số chẵn đôi một khác nhau.
6. \(35\) điểm: Không có ràng buộc bổ sung.

Johnny sưu tập đồ chơi thuộc nhiều loại khác nhau. Anh ấy có thể sở hữu nhiều món cùng loại; các món cùng loại được xem là không phân biệt.

Emma hỏi Johnny có bao nhiêu món đồ chơi. Johnny không muốn tiết lộ nên trả lời bằng một câu đố: nếu mỗi ngày anh chọn một tập con đồ chơi khác với các ngày trước, anh có thể chơi trong đúng \(n\) ngày. Tập rỗng cũng được tính là một tập con hợp lệ. Nói cách khác, trong bộ sưu tập của Johnny có đúng \(n\) tập con khác nhau.

Emma không thích câu trả lời lẫn câu đố này, nhưng vẫn rất muốn biết Johnny có bao nhiêu đồ chơi. Hãy giúp Emma tìm tất cả các khả năng.

Dữ liệu vào

Dòng duy nhất chứa số nguyên \(n\) (\(1\le n\le10^9\)).

Dữ liệu ra

Dòng đầu in số nguyên \(r\), là số khả năng.

Dòng thứ hai in \(r\) số nguyên tăng nghiêm ngặt, là tất cả các tổng số món đồ chơi có thể có.

Ví dụ 1

12

4
4 5 6 11

Giải thích

Johnny có thể có hai xe tải, một ô tô và một máy xúc, tổng cộng \(4\) món; ba xe tải và hai ô tô, tổng cộng \(5\) món; năm xe tải và một ô tô, tổng cộng \(6\) món; hoặc \(11\) xe tải. Với \(11\) xe tải, chẳng hạn, mỗi ngày anh có thể chọn một số lượng khác nhau từ \(0\) đến \(11\).

Ví dụ 2

36

8
6 7 8 10 11 13 18 35

Giải thích

Có hai cách phân loại đồ chơi khác nhau để có tổng cộng \(10\) món: một xe tải, một ô tô và tám máy xúc; hoặc năm xe tải và năm máy xúc. Tuy nhiên, chỉ cần in số lượng món đồ chơi, nên giá trị \(10\) chỉ xuất hiện một lần trong kết quả. Để có tổng cộng \(6\) món, Johnny có thể có một xe tải, một ô tô, hai máy xúc và hai xe buýt.

Phân nhóm

1. \(19\) điểm: \(n\le50\).
2. \(20\) điểm: \(n\le10000\).
3. \(20\) điểm: \(n\le100000\).
4. \(20\) điểm: \(n\le10^8\).
5. \(21\) điểm: Không có ràng buộc bổ sung.

Byteland có \(n\) thành phố (\(n\ge3\)), mỗi thành phố được biểu diễn bởi một điểm khác nhau trên mặt phẳng. Các thành phố được đánh số từ \(1\) đến \(n\). Không có ba thành phố nào thẳng hàng.

Bọc lồi của một tập điểm là đa giác lồi có diện tích nhỏ nhất sao cho mọi điểm đều nằm bên trong hoặc trên biên đa giác. Đa giác lồi có mọi góc nhỏ hơn \(180\) độ và không tự cắt. Hãy tìm số thành phố nằm trên biên của bọc lồi.

Bạn không biết tọa độ các thành phố. Thay vào đó, bạn được phép hỏi hướng quay của bộ ba thành phố phân biệt \((i,j,k)\). Câu trả lời cho biết thứ tự đi qua ba thành phố đó là theo chiều kim đồng hồ hay ngược chiều kim đồng hồ.

Giao diện

Đề gốc dùng thư viện để bài làm truy vấn hướng quay và gửi đáp án. Trên LQDOJ, chương trình vẫn dùng giao diện chữ ký hàm: với C++, bài làm phải định nghĩa void solve(); với Java, bài làm phải định nghĩa static void solve() trong lớp Solution.

Đây là bản chuyển thể trên LQDOJ; bộ kiểm thử được tạo riêng và không phải bộ dữ liệu bí mật chính thức của CEOI 2018.

Grader cung cấp các hàm sau:

int get_n();
bool is_clockwise(int a, int b, int c);
void give_answer(int s);

Với Java, grader cung cấp lớp trilib với các phương thức tĩnh get_n(), is_clockwise(int a, int b, int c) và give_answer(int s) có cùng ý nghĩa.

• get_n() trả về số thành phố.
• is_clockwise(a,b,c) trả về true nếu thứ tự \((a,b,c)\) theo chiều kim đồng hồ, ngược lại trả về false. Ba chỉ số phải đôi một khác nhau và thuộc đoạn \([1,n]\).
• give_answer(s) thông báo rằng có \(s\) thành phố trên biên bọc lồi.

Sau khi gọi give_answer, chương trình phải kết thúc ngay. Hàm này phải được gọi đúng một lần. Không được đọc dữ liệu từ đầu vào chuẩn hoặc ghi dữ liệu ra đầu ra chuẩn.

Các tọa độ được cố định trong suốt quá trình chạy; thư viện trả lời truy vấn một cách xác định. Bạn có thể thử đoán đáp án ngay cả khi chưa chắc chắn.

Dữ liệu vào

Grader đọc dữ liệu kiểm thử trước khi gọi solve(). Bài làm không được đọc dữ liệu từ đầu vào chuẩn.

Dữ liệu ra

Bài làm không được ghi dữ liệu ra đầu ra chuẩn; hãy gọi give_answer(s) đúng một lần.

Thư viện công khai kèm theo đề gốc đọc dữ liệu gồm số thành phố \(n\), sau đó là \(n\) cặp tọa độ. Thư viện này chỉ phục vụ thử nghiệm và khác với thư viện bí mật dùng trên hệ thống chấm chính thức.

Ví dụ

Trong ví dụ, có \(6\) thành phố tại các tọa độ \((1,1)\), \((4,3)\), \((2,2)\), \((1,4)\), \((5,1)\) và \((3,2)\). Bọc lồi có \(4\) đỉnh.

Một số lời gọi tương ứng với ví dụ:

Phân nhóm

Trong tất cả các bộ dữ liệu, \(3\le n\le40000\). Bạn được gọi is_clockwise nhiều nhất \(1000000\) lần.

1. \(15\) điểm: \(n\le50\).
2. \(20\) điểm: \(n\le500\).
3. \(20\) điểm: \(n\le15000\).
4. \(20\) điểm: Có nhiều nhất một thành phố không nằm trên biên bọc lồi.
5. \(25\) điểm: Không có ràng buộc bổ sung.