#P18907. [2026多校联测]axisym

[2026多校联测]axisym

题目描述

对于一个长度为 nn 的排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,其逆排列 qq 满足 qpi=iq_{p_i}=i。

定义

$$\operatorname{sgn}(x)= \begin{cases} 1, & x>0,\\ 0, & x=0,\\ -1, & x<0. \end{cases}$$

则排列 pp 与其逆排列 qq 的差异度为

$$\sum_{i=1}^{n}\bigl[\operatorname{sgn}(p_i-i)\ne\operatorname{sgn}(q_i-i)\bigr],$$

其中 [A][A] 在条件 AA 成立时取 11,否则取 00。

给定常数 kk,若排列 pp 与其逆排列 qq 的差异度不超过 kk,则称排列 pp 是类轴对称的。

给定 n,kn,k 与模数 MM,请你求出:

  1. 长度为 nn 的类轴对称排列的个数;
  2. 所有长度为 nn 的类轴对称排列的逆序对数之和,其中逆序对数指满足 i<ji<j 且 pi>pjp_i>p_j 的下标对 (i,j)(i,j) 的个数。

两个答案均对 MM 取模。

输入格式

一行三个整数 n,k,Mn,k,M,依次表示排列长度、给定的常数和取模的模数。

输出格式

一行两个整数,用一个空格隔开,依次表示类轴对称排列的个数、所有类轴对称排列的逆序对数之和,均对 MM 取模。

样例 1

2 0 1000000007
2 1

样例 2

5 1 1000000007
92 484

样例 3

6 4 998244353
720 5400

样例解释

  • 样例 1:两个排列 (1,2)(1,2) 与 (2,1)(2,1) 的差异度都是 00,都合法;它们的逆序对数分别是 00 与 11,故答案为 22 与 11。
  • 样例 2:合法的排列共有 9292 个,它们的逆序对数之和为 484484。
  • 样例 3:n=6n=6 时差异度最大为 44,故所有 6!=7206!=720 个排列都合法;所有排列的逆序对数之和为 720×152=5400720\times\frac{15}{2}=5400。

子任务

测试点编号 nn kk 分值
1 n≤8n\le8 无特殊限制 10
2-3 无特殊限制 k=0k=0
4-5 k≥n−2k\ge n-2 15
6-10 无特殊限制 65

对于 100%100\% 的数据,2≤n≤10002\le n\le1000,0≤k≤min⁡(n,100)0\le k\le\min(n,100),108≤M≤109+710^8\le M\le10^9+7,且 MM 是质数。