trang chủ / đề bài / unimodarr

Đếm mảng đơn đỉnh

Đề bài

Mô tả

Đếm số lượng mảng thỏa mãn đồng thời các điều kiện sau:

  • Mảng có đúng n phần tử;
  • Mỗi phần tử là số nguyên trong đoạn từ 1 đến m;
  • Trong mảng có đúng một cặp phần tử bằng nhau (nghĩa là có đúng một giá trị xuất hiện hai lần, tất cả các giá trị còn lại đôi một khác nhau);
  • Tồn tại một chỉ số i sao cho mảng tăng ngặt trước vị trí i và giảm ngặt sau vị trí đó. Cụ thể, với mảng a: aj<aj+1 nếu j<i, và aj>aj+1 nếu j≥i.

In ra số lượng mảng thỏa mãn, lấy phần dư khi chia cho 998244353.

Dữ liệu vào

Một dòng chứa hai số nguyên n và m.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng mảng thỏa mãn tất cả các điều kiện, lấy theo modulo 998244353.

Ràng buộc

  • 2≤n≤m≤2·105

Ví dụ

Input Output Giải thích
3 4 6 Sáu mảng: [1,2,1], [1,3,1], [1,4,1], [2,3,2], [2,4,2], [3,4,3].
3 5 10 Chọn hai giá trị phân biệt trong {1,…,5} làm đỉnh và giá trị lặp, có (52)=10 cách.
2 2 0 Với n=2 không thể có mảng vừa tăng ngặt vừa giảm ngặt với một cặp bằng nhau.
42 1337 806066790

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