trang chủ / đề bài / icpc23_mb_g

Dãy con

Đề bài

Mô tả

Cho một xâu S độ dài N và một số nguyên dương K. Hãy đếm số xâu phân biệt có thể thu được bằng cách xóa đúng K ký tự khỏi xâu S. Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo 109+7.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và K: độ dài xâu S và số ký tự cần xóa (2≤N≤2×105, 1≤K≤min(10,N−1)).
  • Dòng thứ hai chứa xâu S độ dài N. Mọi ký tự của xâu đều là chữ cái tiếng Anh in thường.

Dữ liệu ra

In ra đáp án, theo modulo 109+7.

Ràng buộc

  • 2≤N≤2×105
  • 1≤K≤min(10,N−1)
  • S chỉ gồm chữ cái tiếng Anh in thường.

Ví dụ

Input Output Giải thích
9 2
aaabbbccc
6 Các xâu thu được là aaabbbc, aaabbcc, aaabccc, aabbbcc, aabbccc, abbbccc.
6 2
abcabc
15 Cả (62)=15 cách xóa hai ký tự đều cho các xâu khác nhau.

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