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
样例输入 #1
2 998244353
样例输出 #1
4
样例 #2
样例输入 #2
4 100000007
样例输出 #2
32
样例 #3
样例输入 #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 $ .
性质1：如果一个序列是完美的的，当且仅当他排序后所有子区间是好的。
显然。后面考虑时都是把 \(a\) 排序后考虑。
性质2：如果一个序列是完美的的，当且仅当他排序后所有前缀是好的。
进一步的，设整个序列的最小值为 \(l\)，现在考虑前 \(r\) 个数。那么如果一个序列中所有在 \([l,r]\) 中的数的和不超过 \(lr\)，这个序列是好的。因为如果把 \(l\) 加1，(l+1)r，变大，和变小，一定仍然符合要求。
于是我们就有一个 \(O(n^6)\) 的算法。枚举全局最小值，定义 \(dp_{j,s,k}\) 表示现在考虑第 \(j\) 个数，前面的数和为 \(j\)，目前选了 \(k\) 个数。枚举第 \(j\) 个数选了多少个（顺便检查一下条件）。
性质4：\(\forall i,a_i\ge i\)
\(a_1\times i\le\sum\limits_{j=1}^ia_j\le a_1\times a_i\)。
性质5：如果 \(a_i=i\)，那么\(\forall j<i,a_j=i\)
\(a_1i\le\sum\limits_{k=1}^ia_k\le a_1i,a_1=a_2=\cdots =s_k\)
于是分类讨论 \(a_n=n\) 和 \(a_n=n+1\)，前者答案为1（性质5得），现在讨论后者
性质6：\(\sum\limits_{i=1}^n(a_i-a_1)\le n\)
现在就可以把和那一位的复杂度改成 \(n\)，而且枚举的总量为调和级数的，所以复杂度打到了 \(O(n^4log n)\)
性质7：\(a_1\ge n-2\sqrt{n}\)
\(\sum a_i\) 最小是多少？构造应该是 \(a_1\) 个 \(a_1\) 后面跟 \(a_1+2,a_1+3\cdots n+1\)，它们的和为 $$a_1^2+\frac12(a_1+n+3)(n-a_1)\le a_1(n+1)$$
\[a_1^2+n^2\le 2a_1(n+1) \]\[(n-a_1)^2\le 2a_1 \]所以枚举最小值的复杂度缩减为 \(O(\sqrt{n})\)，总复杂度 \((n^3\sqrt nlog n )\)
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,P,dp[N][N],f[N],ans,inv[N],jc;//dp[j][k] 表示选了j个，和为k-j*mn的方案数
int main()
{
scanf("%d%d",&n,&P);
inv[1]=f[0]=f[1]=jc=1;
for(int i=2;i<=n;i++)
{
jc=1LL*jc*i%P;
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
f[i]=1LL*f[i-1]*inv[i]%P;
}
for(int i=max(n-32,1);i<=n;i++)//枚举最小值
{
memset(dp,0,sizeof(dp));
for(int j=1;j<=i;j++)
dp[j][0]=f[j];
for(int j=i+1;j<=n;j++)
{
for(int k=j;k;k--)
{
for(int s=min(i,i*(j-k));~s;s--)
{
for(int c=1;c<=k&&c*(j-i)<=s;c++)
(dp[k][s]+=1LL*dp[k-c][s-c*(j-i)]*f[c]%P)%=P;
}
}
}
for(int j=1;j<n;j++)
for(int k=0;k<=i;k++)
if(k+1LL*(n-j)*(n+1-i)<=i)
(ans+=1LL*dp[j][k]*f[n-j]%P)%=P;
}
printf("%lld",2+ans*1LL*jc%P);
}