A Perfect Problem
Contest: Codeforces Round 752 (Div. 1)
Difficulty rating: 3200
Tags: combinatorics, dp, math

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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2 998244353

Example output:
4

Example input:
4 100000007

Example output:
32

Editorial:
Let's go deeper into the properties of perfect sequences.
Observation $$$1$$$: If a sorted sequence $$$a_1, a_2, \ldots, a_n$$$ is perfect then all its permutations are also perfect.
Actually, it's very easy to see that as the order doesn't matter. So we will work on the sorted version of the sequence.
Observation $$$2$$$: The sorted sequence $$$a_1, a_2, \ldots, a_n$$$ is perfect iff all its subarrays are good.
Proof: Let's fix the $$$\min$$$ and $$$\max$$$ of a subsequence. As $$$\min \cdot \max$$$ is fixed, the worst case happens when we insert as many elements as possible in this subsequence which are in between $$$\min$$$ and $$$\max$$$ as we are comparing $$$\min \cdot \max$$$ with the sum, and the worst case is a subarray of this sorted sequence!
Now we will go one step further.
Observation $$$3$$$: The sorted sequence $$$a_1, a_2, \ldots, a_n$$$ is perfect iff all its prefixes are good.
Proof: The condition essentially means that $$$a_1 \cdot a_i \ge a_1 + a_2 + \ldots +a_i$$$ for all $$$1 \le i \le n$$$. Imagine that its true. Now we will prove that the sequence is perfect. Consider a subarray $$$[i; j]$$$. $$$a_i \cdot a_j \ge a_1 \cdot a_j$$$ $$$\ge a_1 + a_2 + \ldots + a_j$$$ $$$\ge a_i + a_{i+1} + \ldots +a_j$$$. That means all subarrays are good. And following observation $$$2$$$, it indicates that the sequence is perfect. And it is necessary that all the prefixes should be good because they are subarrays after all which proves the iff condition.
Now let's exploit the fact that all $$$a_i$$$ are $$$\le n+1$$$.
Let's remind again that we are considering the sorted sequences for now.
Observation $$$4$$$: $$$a_k \ge k$$$ is required for any $$$k$$$.
Proof: If $$$a_k < k$$$, $$$a_1 + a_2 + \ldots + a_k \ge a_1 + a_1 + \ldots + a_1 \ge a_1 \cdot k \gt a_1 \cdot a_k$$$ (as $$$k \gt a_k$$$) which violates the good condition.
Observation $$$5$$$: If $$$a_k = k$$$, then all $$$a_i = k$$$ for $$$i \le k$$$.
Proof: $$$a_1 \cdot a_k = a_1 \cdot k \ge a_1 + a_2 + \ldots + a_k$$$. This means $$$(a_1 - a_1) + (a_2 - a_1) + \ldots + (a_k - a_1) \le 0$$$. But as all $$$a_i \ge a_1$$$, this can only happen when all $$$a_i = a_1$$$. But as $$$a_k = k$$$, consequently, all $$$a_i$$$ should be $$$k$$$.
So $$$a_n$$$ can be either $$$n$$$ or $$$n+1$$$. If $$$a_n=n$$$ then according to observation $$$5$$$ there is only one such sequence. From now on, let's consider $$$a_n = n + 1$$$.
So $$$a_1 \cdot (n + 1) \ge a_1 + a_2 + \ldots a_n$$$. But this formulation is a bit hard to work on. So now we will make a move which I would like to call a programmer move. That is, the equation is equivalent to $$$(a_1 - a_1) + (a_2 - a_1) + \ldots + (a_n - a_1) \le a_1$$$.
Following observation $$$3$$$, its necessary that $$$a_1 \cdot a_i \ge a_1 + a_2 + \ldots + a_i$$$ for all $$$i$$$.
Observation $$$6$$$: if $$$a_n=n+1$$$ and $$$a_i \ge i+1$$$, then the prefix $$$a_1, a_2, \ldots, a_i$$$ is automatically good if the whole sorted sequence $$$a_1, a_2, \ldots, a_n$$$ is good.
Proof: If the whole sequence is good then, $$$(a_1 - a_1) + (a_2 - a_1) + \ldots + (a_n - a_1) \le a_1$$$. Now, $$$(a_1 - a_1) + (a_2 - a_1) + \ldots + (a_i - a_1) \le (a_1 - a_1) + (a_2 - a_1) + \ldots + (a_n - a_1) \le a_1$$$. So, $$$a_1+a_2+\ldots+a_i \le a_1 \cdot (i+1) \le a_1 \cdot a_i$$$ So the prefix is good!
Let's recap that $$$a_i \ge i$$$ is required(observation $$$4$$$), if $$$a_i \ge i + 1$$$, then $$$a_1, a_2, \ldots, a_i$$$ is automatically good (observation $$$6$$$) and $$$a_i = i$$$ is only possible when $$$i = a_1$$$(observation $$$5$$$).
So the necessary and sufficient conditions for the sorted sequence $$$a$$$ to be perfect assuming $$$a_n = n + 1$$$ are -
• For $$$i \le a_1$$$, $$$a_1 \le a_i \le n + 1$$$
• For $$$i \gt a_1$$$, $$$i + 1 \le a_i \le n + 1$$$
• $$$(a_1 - a_1) + (a_2 - a_1) + \ldots + (a_n - a_1) \le a_1$$$
Notice that we need the answer considering all such sequences, not only sorted sequences, but it is not hard to track that using basic combinatorics. So let's fix the smallest number $$$a_1$$$ and subtract $$$a_1$$$ from everything. So we need to count the number of sequences $$$b_1, b_2, \ldots, b_n$$$ such that -
1. $$$0 \le b_i \le n + 1 - a_1$$$
2. $$$b_1 + b_2 + \ldots b_n \le a_1$$$
3. There is at least $$$1$$$ number $$$\ge n+1-a_1$$$, at least $$$2$$$ numbers $$$\ge n-a_1$$$, $$$\ldots$$$, at least $$$n - a_1$$$ numbers $$$\ge 2$$$ (this condition is basically the intuition of when $$$i \le a_1$$$, $$$a_1 \le a_i \le n + 1$$$ and when $$$i \gt a_1$$$, $$$i + 1 \le a_i \le n + 1$$$).
Let's formulate a dp in top-down manner. We will choose $$$b_i$$$ going from $$$n+1-a_1$$$ to $$$0$$$. Let $$$\operatorname{dp}(i, sum, k) =$$$ number of sequences when we already chose $$$i$$$ elements, the total sum of the selected elements $$$= sum$$$ and we will select $$$k$$$ now. So if we choose $$$cnt$$$ numbers of $$$k$$$, then the transition is something like $$$\operatorname{dp}(i, sum, k)$$$ += $$$\frac{\operatorname{dp}(i + cnt, sum + cnt \cdot k, k - 1)}{cnt!}$$$. And at the base case, when $$$i=n$$$, return $$$n!$$$. The factorial terms are easy to make sense of because we are considering all perfect sequences, not only sorted ones. Check my solution for more clarity.
This dp will take $$$\mathcal{O}(n^4 \cdot \log_2 n)$$$ for each $$$a_1$$$ ($$$\log_2 n$$$ term is for harmonic series sum as $$$cnt \le \frac{a_1}{k}$$$) yielding a total of $$$\mathcal{O}(n^5 \cdot \log_2 n)$$$.
Observation $$$7$$$: If $$$a_1 \lt n - 2 \cdot \sqrt{n}$$$, then no perfect sequences are possible.
Proof: Assume that $$$a_1 \lt n - 2 \cdot \sqrt{n}$$$, or $$$n - a_1 \gt 2 \cdot \sqrt{n}$$$, or $$$n - a_1 \gt 2 \cdot \sqrt{n}$$$. But because of the condition $$$3$$$, there will be at least at least $$$1$$$ number $$$\ge n - 2 \cdot \sqrt{n} + 2$$$, at least $$$2$$$ numbers $$$\ge n - 2 \cdot \sqrt{n} + 1$$$, $$$\ldots$$$, at least $$$n - 2 \cdot \sqrt{n} + 1$$$ numbers $$$\ge 2$$$. But that clearly means that $$$b_1 + b_2 + \ldots b_n \gt n + 1 \gt a_1$$$ which is a contradiction.
So we need to traverse $$$\mathcal{O}(\sqrt{n})$$$ $$$a_1$$$s which also means in the dp $$$k$$$ is also $$$\mathcal{O}(\sqrt{n})$$$. So the total time complexity will be $$$\mathcal{O}(n^3 \sqrt{n} \log_2 n)$$$ or faster but with very low constant that it will work instantly!
Phew, such a long editorial. I need to take a break and explore the world sometimes...