trang chủ / đề bài / icpc25_mt_a

Khu vườn tăng dần

Đề bài

Mô tả

Thiên Sinh là một Người làm vườn Thiên giới trẻ tuổi và đầy tham vọng, được giao chăm sóc một hàng cây thần kỳ đặc biệt. Khu vườn của anh gồm n cây xếp thành hàng, cây thứ i có chiều cao ban đầu ai. Thẩm mỹ của Thiên giới đòi hỏi sự hoàn hảo, và một cuộc kiểm tra lớn sẽ diễn ra sau đúng k ngày nữa.

Để chuẩn bị, Sinh có một công cụ mạnh mẽ: một bình tưới chứa Tinh chất Tăng trưởng Thần thánh. Mỗi ngày, anh thực hiện đúng một lần tưới. Một lần tưới gồm việc chọn một đoạn cây liên tiếp từ chỉ số l đến r (bao gồm cả hai đầu, l≤r) và tưới chúng. Tinh chất mạnh đến mức mọi cây trong đoạn [l,r] được chọn lập tức cao thêm đúng một đơn vị.

Để vượt qua cuộc kiểm tra, khu vườn phải thể hiện "Vẻ đẹp Tăng dần Hoàn hảo", nghĩa là chiều cao cuối cùng của các cây phải tăng ngặt. Tức là sau đúng k ngày tưới, chiều cao cuối cùng a1,a2,…,an phải thỏa mãn a1<a2<…<an.

Thiên Sinh là người lập kế hoạch tỉ mỉ. Anh muốn biết tổng số "lịch tưới" khác nhau mà anh có thể thực hiện để đạt được vẻ đẹp này. Một lịch tưới là một dãy gồm k lần tưới, mỗi ngày một lần. Hai lịch tưới được coi là khác nhau nếu ở một ngày nào đó, đoạn (l,r) được chọn khác nhau.

Cho chiều cao ban đầu của các cây, hãy giúp Sinh tính số lịch tưới hợp lệ khác nhau. Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho 109+7.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên n và k.
  • Dòng thứ hai gồm n số nguyên a1,a2,…,an: chiều cao ban đầu của các cây.

Dữ liệu ra

In ra một số nguyên là số dãy k lần tưới làm cho dãy a tăng ngặt, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 1≤n≤20, 1≤k≤20
  • 1≤ai≤20

Ví dụ

Input Output Giải thích
3 2
1 1 1
2 Có hai lịch tưới hợp lệ: chọn (l,r)=(2,3) ở ngày thứ nhất và (3,3) ở ngày thứ hai; hoặc chọn (3,3) ở ngày thứ nhất và (2,3) ở ngày thứ hai.
3 3
1 1 1
15
5 5
10 9 9 9 10
590

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