Nguồn đề bài: http://vn.spoj.com/problems/DHLOCO/
Nội dung bài viết
1. Đề bài DHLOCO spoj
Carnaval Hạ Long 2015 với chủ đề “Hội tụ tinh hoa – Lan tỏa nụ cười”, điểm mới của lễ hội là sự song hành giữa biểu diễn nghệ thuật “Nơi tinh hoa hội tụ” và diễu hành đường phố “Nụ cười Hạ Long” với sự góp mặt của hơn 2000 diễn viên quần chúng. Có rất nhiều chương trình vui chơi được tổ chức, một trong những trò chơi thu hút được nhiều du khách tham gia đó là trò chơi nhảy lò cò, cụ thể: người chơi cần vượt qua một đoạn đường dài n mét, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là 1 mét, 2 mét, 3 mét. Một cách đi chuyển đúng là dãy các bước nhảy có tổng đúng bằng n.
Yêu cầu: Cho n và M, gọi K là số cách đi chuyển đúng khác nhau để đi hết đoạn đường n mét, hãy tính phần dư của K chia M.
Input
gồm một dòng chứa hai số nguyên dương n, M (M ≤ 2015);
Output
một số nguyên là phần dư của K chia M.
Example
Input:
5 100
Output
13
Ghi chú:
Có 20% số test ứng với 20% số điểm có n ≤ 20;
Có 40% số test ứng với 40% số điểm có n ≤ 106;
Có 40% số test còn lại ứng với 40% số điểm có n ≤ 1015.:
2. Gợi ý DHLOCO spoj Trò chơi lò cò
-Các bạn sử dụng thuật toán nhân ma trận là dễ nhất
3. Code Tham Khảo DHLOCO spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | type matrix=array[1..3,1..3] of int64; const fi=''; fo=''; var f:text; a,b:matrix; n:int64; m:int64; procedure input; begin assign(f,fi); reset(f); readln(f,n,m); close(f); end; function nhan(a,b:matrix):matrix; var c:matrix; k,u,v:longint; begin for u:=1 to 3 do for v:=1 to 3 do begin c[u,v]:=0; for k:=1 to 3 do c[u,v]:=(c[u,v]+a[u,k]*b[k,v])mod m; end; exit(c); end; function luythua(a:matrix;k:int64):matrix; var b:matrix; begin if k=1 then exit(a) else begin b:=luythua(a,k div 2); b:=nhan(b,b); if k mod 2 =1 then b:=nhan(b,a); end; exit(b); end; procedure solve; begin a[1,1]:=0; a[1,2]:=1; a[1,3]:=0; a[2,1]:=0; a[2,2]:=0; a[2,3]:=1; a[3,1]:=1; a[3,2]:=1; a[3,3]:=1; b:=luythua(a,n-1); end; procedure output; begin assign(f,fo); rewrite(f); case n of 1: writeln(f,1); 2: writeln(f,2 mod m); 3: writeln(f,4 mod m); else begin solve; writeln(f,(b[1,1]+b[1,2]*2+b[1,3]*4)mod m); end; end; close(f); end; BEGIN input; output; END. |
Bài viết liên quan
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PBCSEQ SPOJ – Các đoạn nguyên
- VDANGER SPOJ- Nguy hiểm rõ ràng trước mắt
- TNHWIFI spoj – Cafe wifi
- NKH spoj – Tách Từ
- MPILOT spoj – Pilots
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- V8ORG spoj – Tổ chức đối lập
- STMERGE spoj – VOI 2013 – Trộn xâu