trang chủ / đề bài / icpc21_mb_f

Thiệp chúc mừng

Đề bài

Mô tả

Ở một ngôi làng nọ, N hộ gia đình sống quây quần thành một vòng tròn, đánh số từ 0 đến N−1. Ban đầu, mức độ hạnh phúc của hộ thứ i là Ai (0≤i<N). Mỗi buổi sáng, mỗi hộ viết thiệp chúc mừng gửi cho các hộ khác, nhưng hẹn để thiệp chỉ đến tay người nhận sau giờ làm việc. Sau giờ làm, ai cũng mệt mỏi nên mức độ hạnh phúc của họ chỉ còn phụ thuộc vào những tấm thiệp nhận được: mức độ hạnh phúc của một hộ vào cuối ngày bằng tổng mức độ hạnh phúc của những người gửi thiệp cho hộ đó, tính tại thời điểm thiệp được viết.

Vào ngày 0, mỗi hộ chỉ viết thiệp cho hai hộ kề bên. Ở mỗi ngày tiếp theo, khoảng cách gửi thiệp tăng gấp đôi. Cụ thể, vào ngày t, hộ i viết thiệp cho hộ (i+2t)modN và hộ (i−2tmodN+N)modN. Một hộ có thể viết hai tấm thiệp cho cùng một hộ trong cùng một ngày.

Cho số nguyên K, hãy tính mức độ hạnh phúc của mọi hộ sau 2K ngày (tức là vào cuối ngày 2K−1).

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và K.
  • Dòng tiếp theo chứa N số nguyên A0,A1,…,AN−1.

Dữ liệu ra

In ra một dòng gồm N số nguyên là mức độ hạnh phúc của các hộ 0,1,…,N−1 sau 2K ngày, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 2≤N≤105.
  • 0≤K≤109.
  • 1≤Ai≤109.

Ví dụ

Input Output Giải thích
3 0
1 2 3
5 4 3 Chỉ có ngày 0: hộ 0 nhận thiệp từ hộ 2 và hộ 1 nên có 3+2=5; tương tự hộ 1 có 1+3=4, hộ 2 có 2+1=3.
3 1
1 2 3
7 8 9 Sau ngày 0 các mức là 5,4,3. Ngày 1 khoảng cách là 2: hộ 0 nhận từ hộ 1 và hộ 2 nên có 4+3=7; hộ 1 có 3+5=8, hộ 2 có 5+4=9.

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