308954: CF1603E. A Perfect Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A Perfect Problem

题意翻译

一个序列是好的当且仅当集合最大值乘上集合最小值大于等于集合元素的加和; 一个序列是完美的,当且仅当这个序列的任何子序列都是好的(包括自己不包括空集); 你要求的是:长度为 $n$ 的并且每一个元素都大于等于 $1$ 并且小于等于 $n+1$ 的完美序列的个数对 $\mathrm{mod}$ 取模。

题目描述

A sequence of integers $ b_1, b_2, \ldots, b_m $ is called good if $ max(b_1, b_2, \ldots, b_m) \cdot min(b_1, b_2, \ldots, b_m) \ge b_1 + b_2 + \ldots + b_m $ . A sequence of integers $ a_1, a_2, \ldots, a_n $ is called perfect if every non-empty subsequence of $ a $ is good. YouKn0wWho has two integers $ n $ and $ M $ , $ M $ is prime. Help him find the number, modulo $ M $ , of perfect sequences $ a_1, a_2, \ldots, a_n $ such that $ 1 \le a_i \le n + 1 $ for each integer $ i $ from $ 1 $ to $ n $ . A sequence $ d $ is a subsequence of a sequence $ c $ if $ d $ can be obtained from $ c $ by deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式


The first and only line of the input contains two space-separated integers $ n $ and $ M $ ( $ 1 \le n \le 200 $ ; $ 10^8 \le M \le 10^9 $ ). It is guaranteed that $ M $ is prime.

输出格式


Print a single integer — the number of perfect sequences modulo $ M $ .

输入输出样例

输入样例 #1

2 998244353

输出样例 #1

4

输入样例 #2

4 100000007

输出样例 #2

32

输入样例 #3

69 999999937

输出样例 #3

456886663

说明

In the first test case, the perfect sequences are $ [2, 2] $ , $ [2, 3] $ , $ [3, 2] $ and $ [3, 3] $ . In the second test case, some of the perfect sequences are $ [3, 4, 3, 5] $ , $ [4, 5, 4, 4] $ , $ [4, 5, 5, 5] $ etc. One example of a sequence which is not perfect is $ [2, 3, 3, 4] $ , because, for example, the subsequence $ [2, 3, 4] $ is not an good as $ 2 \cdot 4 < 2 + 3 + 4 $ .

Input

题意翻译

一个序列是好的当且仅当集合最大值乘上集合最小值大于等于集合元素的加和; 一个序列是完美的,当且仅当这个序列的任何子序列都是好的(包括自己不包括空集); 你要求的是:长度为 $n$ 的并且每一个元素都大于等于 $1$ 并且小于等于 $n+1$ 的完美序列的个数对 $\mathrm{mod}$ 取模。

加入题单

上一题 下一题 算法标签: