trang chủ / đề bài / icpc23_mn_f

Lũy thừa Fibonacci

Đề bài

Mô tả

Giữa lòng một khu rừng cổ, nhà thám hiểm Phù thủy Minh bắt đầu hành trình giải những câu đố bí ẩn. Một cuốn nhật ký gia truyền tiết lộ một thông điệp: kho báu được canh giữ bởi các câu đố toán học gắn với dãy Fibonacci.

Nhắc lại, dãy Fibonacci được định nghĩa như sau:

  • F(0)=0
  • F(1)=1
  • F(i)=F(i−2)+F(i−1) với mọi i≥2.

Để mở kho báu, Minh cần nhanh chóng tính tổng S của lũy thừa bậc k của n số Fibonacci đầu tiên:

S=∑i=1nF(i)k

Cho n và k, hãy giúp Minh tính S modulo 998244353.

Dữ liệu vào

Một dòng gồm hai số nguyên n và k (1≤n≤1018, 1≤k≤106).

Dữ liệu ra

In ra giá trị S modulo 998244353.

Ràng buộc

  • 1≤n≤1018
  • 1≤k≤106

Ví dụ

Input Output Giải thích
3 2 6 F(1)2+F(2)2+F(3)2=12+12+22=6.
5 1 12 F(1)+F(2)+F(3)+F(4)+F(5)=1+1+2+3+5=12.
1000 1000 954643773

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0