[R50F]平衡数组 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

一个长度为 $n$ 的数组 $a$ 被称为平衡的，当且仅当它同时满足以下两个条件：

1. 对于所有 $1 \leq i \leq n$，均有 $1 \leq a_i \leq n$。
2. 定义一个长度同样为 $n$ 的数组 $b$，其中 $b_i$ 表示数组 $a$ 中值大于等于 $i$ 的元素数量。要求对于所有 $1 \leq i \leq n$，均有 $a_i = b_i$（即数组 $a$ 和数组 $b$ 完全相同）。

定义一个数组的平衡值为：该数组中不同数字的个数。

现在给定正整数 $N$ 和 $P$，请你求出所有满足元素总和恰好为 $N$ 的平衡数组的平衡值之和，并将结果对 $P$ 取模。

格式

输入格式

第一行包含两个正整数 $N$ 和 $P$，分别表示要求的元素总和以及取模的模数。

输出格式

输出一行一个整数，表示所有满足条件的平衡数组的多样性之和对 $P$ 取模后的结果。

样例

样例输入 #1

5 100000007

样例输出 #1

2

样例解释 #1

满足条件的数组为：

1. $[3,1,1]$。

故平衡值为 $2$。

样例输入 #2

10 20

样例输出 #2

7

样例解释 #2

满足条件的数组为：

1. $[5,2 , 1, 1, 1]$。
2. $[4, 3, 2, 1]$。

故平衡值为 $3 + 4 = 7$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$N\le$	子任务依赖
$1$	$20$	$20$	无
$2$	$40$	$2000$	$1$
$3$	$40$	$10^5$	$1, 2$

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$2 \le P \le 10^9$。