- 如果 $max(a_1,a_2,\cdots,a_m)\cdot min(a_1,a_2,\cdots,a_m)\geq a_1+a_2+\cdots+a_m$，则整数序列 $a_1,a_2,\cdots,a_m$ 被称为好的。
- 如果 $a$ 的每个非空子序列都是好的，则整数序列 $a_1,a_2,\cdots,a_n$ 被称为完美的。
- 给定两个整数 $n$ 和 $M$，$M$ 是素数。求完美序列 $a_1,a_2,\cdots,a_n$ 且每项满足 $1\leq a_i\leq n+1$ 的数量，对 $M$ 取模。
- $1\leq n\leq 200,10^8\leq M\leq 10^9$。
sol
- 可以发现 一个序列是完美的 等价于 将它从小到大排序后的序列是完美的（即顺序无关）。
判断一个从小到大的序列是否是完美的
-
以下的序列，$a$ 都是从小到大的序列。
-
发现这等价于这个序列的所有前缀都是好的。
- 假设选出的子序列的最小/最大下标分别为 $l,r$，那么 $mul\geq a_1\cdot a_r\geq a_1+a_2+\cdots a_r\geq sum$。
-
这还不够，我们再找一些条件。
- $a_k\geq k$。
- 如果不满足，则 $a_1\cdot a_k<a_1\cdots k<a_1+a_2+\cdots a_r$ 矛盾。
- 若存在 $a_k=k$，则 $a_1=a_2=\cdots=a_k=k$。
- $a_1\cdot a_k=a_1\cdot k\geq a_1+a_2+\cdots a_r$，即 $(a_1-a_1)+(a_2-a_1)+\cdots+(a_k-a_1)\leq 0$，而 $a_i\geq a_1$，所以 $a_i=k$。
- 可以发现 $a_n=n$ 只有一种方案，否则 $a_n=n+1$。
- 如果 $a_n=n+1,a_i\geq i+1$，那么整个序列是完美的 等价于 整个序列是好的。
- 整个序列是好的当且仅当 $(a_1-a_1)+(a_2-a_1)+\cdots+(a_n-a_1)\leq a_1$。
- 整个序列是完美的显然必须满足整个序列是好的。
- 考虑前缀 $1..k$，它是好的当且仅当 $(a_1-a_1)+(a_2-a_1)+\cdots+(a_k-a_1)\leq a_1\cdot (a_k-k)$，若满足 $(a_1-a_1)+(a_2-a_1)+\cdots+(a_n-a_1)\leq a_1$（整个序列是好的） 则一定满足上述条件，而每个前缀都是好的所以整个序列是完美的。
- 如果 $a_n=n+1,a_i\geq i$，那么整个序列是完美的 等价于 满足条件 2，且整个序列是好的。
- 满足条件 2，假设 $a_1=a_2=\cdots=a_k=k$，对于长度不超过 $k$ 的前缀显然都是好的。
- 长度超过 $k$ 的前缀证明和 3 类似。
从小到大的完美序列的方案数
-
固定 $a_1$ 的值：
- $a_1\leq a_2\leq \cdots \leq a_n$。
- 对于 $i\leq a_1$，$a_1\leq a_i\leq n+1$
- $a_2\cdots a_{i-1}$ 不能 $<a_1$，否则就和单调性（从小到大）矛盾。
- $a_{a_1}$ 可以是 $a_{a_1}$ 也可以是更大的数。
- 你也可以把这个条件当成：对于 $i\lt a_1$，$i+1\leq a_i\leq n+1$ 且 $a_1\leq a_{a_1}\leq n+1$，但是这个形式不便于之后的计算。
- 对于 $i>a_1$，$i+1\leq a_i\leq n+1$
- $a_i$ 不能取 $i$，否则就和 $a_1$ 的值矛盾（条件2）。
-
$(a_1-a_1)+(a_2-a_1)+\cdots+(a_n-a_1)\leq a_1$。
-
设 $b_i=a_i-a_1$，那么：
- $b_1=0$
- $b_1\leq b_2\leq \cdots \leq b_n$
- $0\leq b_i\leq n+1-a_1$
- $b_1+b_2+\cdots+b_n\leq a_1$
- $b_n\geq n+1-a_1$，$b_{n-1}\geq n-a_1$，...，$b_{a_1+1}\geq 2$
- 显然固定 $a_1$ 后，$b$ 和 $a$ 是一一对应的。
-
由于需要满足 $b_n\geq n+1-a_1$，$b_{n-1}\geq n-a_1$，...，$b_{a_1+1}\geq 2$ 和 $b_1+b_2+\cdots+b_n\leq a_1$ 这两个条件，$a_1$ 大概只有 $O(\sqrt n)$ 种取值。
- 枚举发现 $n$ 取最大值 $200$ 时，$a_1\geq n-17$。
完美序列的方案数
- 即上面的做法的 $b$ 顺序可以任意排列。
- 依旧固定 $a$ 的最小值 $x(x\geq n-17)$：
- 设 $b_i=a_i-x$，那么：
- $\exists k,b_k=0$
- $0\leq b_i\leq n+1-x$
- $b_1+b_2+\cdots+b_n\leq x$
- $\geq 1$ 个数 $\geq n+1-x$，$\geq 2$ 个数 $\geq n-x$，...，$\geq n-x$ 个数 $\geq 2$。
这等价于 $\leq x$ 个数 $\leq 1$，$\leq x+1$ 个数 $\leq 2$，...，$\leq n-1$ 个数 $\leq n-x$（再加个 $\leq n$ 个数 $\leq n+1-x$ 也不影响）。
- 对 $b$ 计数，设 $dp[i][j][k]$ 表示考虑完值 $\leq i$ 的位置，共选了 $j(j\leq x+i-1)$ 个数，选的数之和为 $k$ 的方案数。转移枚举有 $t$ 个值为 $i$ 的位置，从 $\frac{dp[i-1][j-t][k-i*t]}{t!}$ 转移过来。除这个阶乘是因为组合数选位置，最后计算答案要乘上 $n!$。
- 设 $b_i=a_i-x$，那么：
- 实现时可以使用记忆化，实际用到的状态并不多。理论时间复杂度为 $O(n^3\sqrt n\log n)$。
```cpp
include
using namespace std;
typedef long long ll;
int n,Mod,x;
ll fac[210],inv[210];
int dp[210][210][210];
int solve(int i,int j,int k){
if (!i) return (k?0:(!j?0:inv[j]));
if (j>x+i-1) return 0;
if (~dp[i][j][k]) return dp[i][j][k];
int res=0;
for (int t=0;t<=j&&it<=k;t++)
res=(res+solve(i-1,j-t,k-it)inv[t])%Mod;
dp[i][j][k]=res; return res;
}
int main(){
scanf("%d%d",&n,&Mod);
fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]i%Mod;
inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(Mod-Mod/i)inv[Mod%i]%Mod;
inv[0]=1; for (int i=1;i<=n;i++) inv[i]=inv[i-1]inv[i]%Mod;
int ans=0;
for (x=max(1,n-17);x<=n+1;x++){
memset(dp,-1,sizeof(dp));
for (int k=0;k<=x;k++) ans=(ans+solve(n+1-x,n,k))%Mod;
}
printf("%lld\n",ans*fac[n]%Mod);
return 0;
}
```