#P18907. [2026多校联测]axisym
[2026多校联测]axisym
题目描述
对于一个长度为 的排列 ,其逆排列 满足 。
定义
$$\operatorname{sgn}(x)= \begin{cases} 1, & x>0,\\ 0, & x=0,\\ -1, & x<0. \end{cases}$$则排列 与其逆排列 的差异度为
$$\sum_{i=1}^{n}\bigl[\operatorname{sgn}(p_i-i)\ne\operatorname{sgn}(q_i-i)\bigr],$$其中 在条件 成立时取 ,否则取 。
给定常数 ,若排列 与其逆排列 的差异度不超过 ,则称排列 是类轴对称的。
给定 与模数 ,请你求出:
- 长度为 的类轴对称排列的个数;
- 所有长度为 的类轴对称排列的逆序对数之和,其中逆序对数指满足 且 的下标对 的个数。
两个答案均对 取模。
输入格式
一行三个整数 ,依次表示排列长度、给定的常数和取模的模数。
输出格式
一行两个整数,用一个空格隔开,依次表示类轴对称排列的个数、所有类轴对称排列的逆序对数之和,均对 取模。
样例 1
2 0 1000000007
2 1
样例 2
5 1 1000000007
92 484
样例 3
6 4 998244353
720 5400
样例解释
- 样例 1:两个排列 与 的差异度都是 ,都合法;它们的逆序对数分别是 与 ,故答案为 与 。
- 样例 2:合法的排列共有 个,它们的逆序对数之和为 。
- 样例 3: 时差异度最大为 ,故所有 个排列都合法;所有排列的逆序对数之和为 。
子任务
| 测试点编号 | 分值 | ||
|---|---|---|---|
| 1 | 无特殊限制 | 10 | |
| 2-3 | 无特殊限制 | ||
| 4-5 | 15 | ||
| 6-10 | 无特殊限制 | 65 |
对于 的数据,,,,且 是质数。