Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
VMYT - Hành trình đến đảo dừa |
) nhưng khổ nỗi vương quốc dừa dùng điện năng lượng mặt trời nên không có đủ điện để chạy siêu máy tính được. Thế là giờ chỉ còn mỗi cái Laptop Pentium 3 800Mhz là có thể dùng được. Bạn là một nhà lập trình viên siêu hạng, hãy giúp yenthanh132 và chứng tỏ rằng Laptop cùi tới mấy mà biết sử dụng thì cũng có thể làm nên chuyện :)
Yêu cầu:
- Cho số N, K và dãy số a[1], a[2],... , a[K] - số đảo dừa trong vương quốc qua K năm đầu
- Với i>K ta có a[i] = a[i-1] * a[i-2] * a[i-3] * ... * a[i-K];
- Tính a[N], do số lượng hòn đảo rất lớn nên yenthanh132 chỉ yêu cầu bạn tính phần dư của kết quả khi chia cho số 1000000007 ( = 10^9 + 7). Tức là tính a[N] % 1000000007
Lưu ý: Những đường dẫn đến bài tập bên ngoài chỉ mang tính chất tham khảo cho vui, không liên quan đến bài này.
Input
- Dòng đầu tiên gồm hai số nguyên dương N, K.
- Dòng thứ hai ghi K số nguyên dương, số thứ i của dãy số là Ai
Giới hạn
- 1 ≤ N ≤ 109
- 1 ≤ K ≤ 50 và K < N.
- 1 ≤ Ai ≤ 109
- 30% số test có N ≤ 100000
Output
- Ghi ra kết quả theo modulo 1000000007 (109 + 7).
Chấm bài
Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.
Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.
Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.
Example
Input:
7 3
1 2 3 Output:
139968
Được gửi lên bởi: | VOJ Team |
Ngày: | 2013-06-19 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC |
Nguồn bài: | VM13 - Lê Yên Thanh |
hide comments
2019-12-23 12:12:27
Có ai giống tôi không? Nhớ dùng định lí Fermat nhỏ mà quên reset ma trận khi nhân! Thật là đắng mà :(( (10đ) |
|
2019-07-28 10:59:26
Lại quên mod . Ai làm nhớ để mod mọi nơi nha. Chú ý sử dụng định lý fermat để xử lý số mũ. Lời khuyên chân thành từ một bạn nam đẹp trai không tiện nói tên :))) |
|
2019-05-16 10:57:05
nếu bạn 10d còn quan tâm, vì (a^b)%MOD khác hoàn toàn (a^(b%MOD))%MOD. |
|
2018-07-25 07:57:29
. Last edit: 2018-07-25 07:57:41 |
|
2018-02-20 11:13:43
Em ko dùng fermat và bị 10đ ! Tại sao vậy ạ ? |
|
2017-09-30 06:56:25
{dinh truong lam} cái fermat chết tiệt làm mất cả buổi sáng mới 100d |
|
2015-11-11 16:15:57 lucky++
Last edit: 2015-11-19 06:14:59 |
|
2015-10-27 09:27:31 Prismatic
one hit :)) |
|
2014-07-02 02:37:02 Tây Cuồng
Cảm ơn anh (chị) Bit |
|
2013-07-12 12:52:27 an IM3 Ex-Member of Bit
http://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_nh%E1%BB%8F_Fermat |