Hoán vị hạnh phúc

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho hoán vị $p_{1}, p_{2}, \dots, p_{n}$ của ${1, 2, \dots, n}$ . Một đoạn $[l, r]$ (với $1 \leq l \leq r \leq n$ ) được gọi là đoạn đẹp nếu

$max (p_{l}, p_{l + 1}, \dots, p_{r}) - min (p_{l}, p_{l + 1}, \dots, p_{r}) = r - l .$

Nói cách khác, các phần tử trong đoạn tạo thành một dãy số nguyên liên tiếp (theo thứ tự nào đó). Đặc biệt, mọi đoạn $[i, i]$ đều là đoạn đẹp.

Độ hạnh phúc của hoán vị $p$ là số cặp $(l, r)$ mà $[l, r]$ là đoạn đẹp.

Cho hai số nguyên $n$ và $m$ . Hãy tính tổng độ hạnh phúc của tất cả $n!$ hoán vị độ dài $n$ , lấy dư cho số nguyên tố $m$ .

Dữ liệu vào

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

Dữ liệu ra

In ra một số nguyên $r$ ( $0 \leq r < m$ ) — tổng độ hạnh phúc lấy dư cho $m$ .

Ràng buộc

$1 \leq n \leq 250 000$
$10^{8} \leq m \leq 10^{9}$ , $m$ là số nguyên tố.

Ví dụ

Input	Output	Giải thích
1 993244853	1	Chỉ có hoán vị $[1]$ với đúng 1 đoạn đẹp.
2 993244853	6	Hai hoán vị $[1, 2]$ và $[2, 1]$ , mỗi cái có 3 đoạn đẹp ⇒ tổng $6$ .
3 993244853	32	Sáu hoán vị độ dài 3 cho tổng độ hạnh phúc $6 + 5 + 5 + 5 + 5 + 6 = 32$ .
2020 437122297	265955509

Bình luận

Không có bình luận tại thời điểm này.