CSES - Counting Reorders | Đếm số cách sắp xếp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Tính số cách có thể sắp xếp lại các ký tự của một chuỗi sao cho không có hai ký tự liền kề nào giống nhau.

Ví dụ, kết quả cho aabc là \(6\), vì các thứ tự có thể là abac, abca, acab, acba, baca và caba.

Input

  • Một dòng duy nhất chứa một chuỗi \(n\) ký tự từ a - z.

Output

  • Một số nguyên duy nhất: kết quả sau khi được modulo cho \(10^9 + 7\).

Constraints

  • \(1\leq n \leq 5000\)

Example

Sample input

aabc

Sample output

6

Bình luận


  • -1
    vanphukhang_0604    10:09 p.m. 14 Tháng 8, 2023 ← chỉnh sửa 2

    CSES - Counting Reorders | Đếm số cách sắp xếp

    Tính số cách có thể sắp xếp lại các ký tự của một xâu sao cho không có hai ký tự liền kề nào giống nhau.

    Ví dụ, có \(6\) cách sắp xếp thoả mãn cho xâu aabc, bao gồm abac, abca, acab, acba, baca và caba.

    Input

    • Một dòng duy nhất chứa một xâu gồm \(n \ (1 \leq n \leq 5000)\) kí tự từ a - z.

    Output

    • In ra một số nguyên là số cách sắp xếp sau khi chia lấy dư cho \(10^9+7\).

    Example

    Test 1

    Input 
    aabc
    Output 
    6
      • 2 bình luận nữa