← 返回题目列表

Codeforces · 1542/E1

E1. 异常排列对(简易版)

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

这是问题的简单版本。简单版本和困难版本之间的唯一区别是对 $$$n$$$ 的限制。只有解决了两个版本的问题,你才能进行黑客攻击。

$$$1, 2, \ldots, n$$$ 的排列是 $$$n$$$ 整数的序列,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。例如,$$$[2,3,1,4]$$$ 是 $$$1, 2, 3, 4$$$ 的排列,但 $$$[1,4,2,2]$$$ 不是,因为 $$$2$$$ 在其中出现了两次。

回想一下,排列 $$$a_1, a_2, \ldots, a_n$$$ 中的反转数量是索引对 $$$(i, j)$$$ 的数量,使得 $$$i < j$$$ 且 $$$a_i > a_j$$$。

令 $$$p$$$ 和 $$$q$$$ 为 $$$1, 2, \ldots, n$$$ 的两个排列。求满足以下条件的排列对 $$$(p,q)$$$ 的数量:

- $$$p$$$ 按字典顺序小于 $$$q$$$。
- $$$p$$$ 中的反转数量大于 $$$q$$$ 中的反转数量。

打印以 $$$mod$$$ 为模的此类对的数量。请注意,$$$mod$$$ 可能不是素数。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$mod$$$ ($$$1\le n\le 50$$$, $$$1\le mod\le 10^9$$$)。

输出

打印一个整数,它是对 $$$mod$$$ 取模的答案。

示例

输入 #1

4 403458273

输出 #1

17

注意

以下是当 $$$n=4$$$ 时所有有效的对 $$$(p,q)$$$。

- $$$p=[1,3,4,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,2,3]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,4,3]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,3,1,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,3,4,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,1,3]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,4,2]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,2,1,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,2,4,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,1,2]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,3,2]$$$,
- $$$p=[3,4,2,1]$$$,$$$q=[4,2,1,3]$$$。