trang chủ / đề bài / icpc20_nat_i

Mảng hai chiều vô hạn

Đề bài

Mô tả

Ta định nghĩa một mảng hai chiều vô hạn F theo công thức sau:

  • F0,0=0,
  • F0,1=F1,0=1,
  • Với i≥2: Fi,0=Fi−1,0+Fi−2,0,
  • Với i≥2: F0,i=F0,i−1+F0,i−2,
  • Với i,j≥1: Fi,j=Fi−1,j+Fi,j−1.

Dưới đây là một vài giá trị đầu tiên của F (hàng i, cột j):

Fi,j j=0 j=1 j=2 j=3 j=4 j=5
i=0 0 1 1 2 3 5
i=1 1 2 3 5 8 13
i=2 1 3 6 11 19 32
i=3 2 5 11 22 41 73
i=4 3 8 19 41 82 155
i=5 5 13 32 73 155 310

Cho x và y, hãy tính Fx,y.

Dữ liệu vào

Một dòng duy nhất gồm hai số nguyên x và y (0<x,y<106).

Dữ liệu ra

In ra một số nguyên là giá trị Fx,y theo modulo 109+7.

Ràng buộc

  • 0<x,y<106

Ví dụ

Input Output Giải thích
2 2 6 F2,2=F1,2+F2,1=3+3=6.
1 5 13 F1,5=13 (xem bảng).

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