trang chủ / đề bài / icpc23_mb_c

Dãy đẹp

Đề bài

Mô tả

Cho tập hợp A gồm một số số nguyên trong phạm vi từ 1 đến 8. Xét dãy gồm n số nguyên [a1;a2;…;an], mỗi số được chọn từ tập A.

Ta gọi dãy này là đẹp nếu với mọi số x, các phần tử của dãy bằng x cách nhau ít nhất x vị trí. Nói cách khác, với mọi số x và mọi cặp chỉ số 1≤i<j≤n sao cho ai=aj=x, ta luôn có j−i≥x.

Hãy đếm số dãy đẹp với n và tập A cho trước. Vì số này rất lớn, hãy tính nó theo modulo 109+7.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m: độ dài dãy và số phần tử của tập A (1≤n≤100, 1≤m≤8).

Dòng thứ hai chứa m số nguyên phân biệt theo thứ tự tăng dần: các phần tử của tập A (1≤ai≤8, ai<ai+1).

Dữ liệu ra

In ra số dãy đẹp, theo modulo 109+7.

Ràng buộc

  • 1≤n≤100
  • 1≤m≤8
  • 1≤ai≤8, ai<ai+1

Ví dụ

Input Output Giải thích
3 2
1 2
5 Các dãy đẹp là [1;1;1], [1;1;2], [1;2;1], [2;1;1], [2;1;2].
5 3
1 2 3
75 Chẳng hạn [3;1;2;3;1] là dãy đẹp, còn [3;2;3;1;1] không đẹp vì hai số 3 chỉ cách nhau 2 vị trí.

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