trang chủ / đề bài / icpc26_mt_g

Kim tự tháp Pascal

Đề bài

Mô tả

Một công trình gồm n tầng và sử dụng n loại khối lập phương, được đánh số từ 1 đến n. Khối lập phương loại k có cạnh dài k, nên thể tích của mỗi khối loại k là k3.

Số khối lập phương cần dùng để xây mỗi tầng tuân theo tam giác Pascal, từ trên xuống dưới:

  • Tầng thứ nhất gồm 1 khối loại 1.
  • Tầng thứ hai gồm 2 khối: 1 khối loại 1 và 1 khối loại 2.
  • Tầng thứ ba gồm 4 khối: 1 khối loại 1, 2 khối loại 2 và 1 khối loại 3.
  • Tầng thứ tư gồm 8 khối: 1 khối loại 1, 3 khối loại 2, 3 khối loại 3 và 1 khối loại 4.
  • Công trình tiếp tục được xây theo cùng quy luật đó.

Số khối lập phương trên bốn tầng đầu tiên được sắp xếp như sau:

1
1 1
1 2 1
1 3 3 1

Ở đây, số ở vị trí thứ k của tầng thứ n là số khối lập phương loại k của tầng đó.

Yêu cầu: Hãy tính tổng thể tích của tất cả các khối lập phương cần dùng để xây tầng thứ n.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương n (1≤n≤1018).

Dữ liệu ra

In ra tổng thể tích của tất cả các khối lập phương trên tầng thứ n, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 1≤n≤1018.

Ví dụ

Input Output Giải thích
3 44 Tầng thứ ba gồm 1 khối loại 1, 2 khối loại 2 và 1 khối loại 3. Tổng thể tích là 13+2×23+33=1+16+27=44.
4 170 Tầng thứ tư gồm 1 khối loại 1, 3 khối loại 2, 3 khối loại 3 và 1 khối loại 4. Tổng thể tích là 13+3×23+3×33+43=1+24+81+64=170.

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