trang chủ / bài tập / 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 ji.

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 nm.

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

  • 2nm2·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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0