← 返回题目列表

Codeforces · 1284/C

C. 新年和排列

中文机器翻译题面 查看原题

回想一下,排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

序列 $$$a$$$ 是序列 $$$b$$$ 的子段,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。我们将子段表示为 $$$[l, r]$$$,其中 $$$l, r$$$ 是两个整数,$$$1 \le l \le r \le n$$$。这表示从序列中删除开头的 $$$l-1$$$ 元素和结尾的 $$$n-r$$$ 元素的子段。

对于排列 $$$p_1, p_2, \ldots, p_n$$$,我们将框架段定义为子段 $$$[l,r]$$$,其中 $$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$$$。例如,对于排列 $$$(6, 7, 1, 8, 5, 3, 2, 4)$$$,其一些框架段是:$$$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$$$。特别是,子段 $$$[i,i]$$$ 始终是 $$$1$$$ 和 $$$n$$$(含)之间的任何 $$$i$$$ 的框架段。

我们将排列$$$p$$$的幸福度定义为$$$(l, r)$$$对的数量,使得$$$1 \le l \le r \le n$$$,并且$$$[l, r]$$$是一个框架段。例如,排列 $$$[3, 1, 2]$$$ 的幸福度为 $$$5$$$:除了 $$$[1, 2]$$$ 之外的所有段都是框架段。

给定整数 $$$n$$$ 和 $$$m$$$,Jongwon 想要计算长度为 $$$n$$$ 的所有排列的幸福感之和,并对质数 $$$m$$$ 取模。请注意,存在 $$$n!$$$($$$n$$$ 的阶乘)长度为 $$$n$$$ 的不同排列。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 250\,000$$$,$$$10^8 \le m \le 10^9$$$,$$$m$$$ 是质数)。

输出

打印 $$$r$$$ ($$$0 \le r < m$$$),长度为 $$$n$$$ 的所有排列的幸福感之和,以质数 $$$m$$$ 为模。

示例

输入 #1

1 993244853

输出 #1

1

输入 #2

2 993244853

输出 #2

6

输入 #3

3 993244853

输出 #3

32

输入#4

2019 993244853

输出#4

923958830

输入 #5

2020 437122297

输出 #5

265955509

注意

对于样本输入 $$$n=3$$$,让我们考虑长度为 $$$3$$$ 的所有排列:

- $$$[1, 2, 3]$$$,所有子段都是框架段。幸福是$$$6$$$。
- $$$[1, 3, 2]$$$,除 $$$[1, 2]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[2, 1, 3]$$$,除 $$$[2, 3]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[2, 3, 1]$$$,除 $$$[2, 3]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[3, 1, 2]$$$,除 $$$[1, 2]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[3, 2, 1]$$$,所有子段都是框架段。幸福是$$$6$$$。

因此,幸福感的总和是$$$6+5+5+5+5+6 = 32$$$。