solution
考虑寻求存在满足条件的排列 P 的充要的条件。
首先显然的是假设整个序列的 LIS 长度为 k,那么 A_i\in\{k-1,k\},因为去掉一个 LIS 里的数之后剩下的 k-1 个数仍然构成 LIS,长度至少为 k-1,并且还可能去掉后无影响即长度为 k。
下面定义必经点、非必经点、无用点。
- 若位置 i 在所有 LIS 中,即去掉位置 i 后 LIS 长度减少,那么称 i 为必经点,有 A_i=k-1。
- 若位置 i 在某个 LIS 中,且去掉位置 i 后 LIS 长度不变,那么称 i 为非必经点,有 A_i=k。
- 若位置 i 不在任何一个 LIS 中,那么称 i 为无用点,有 A_i=k。
首先我们考虑整个 A 序列都是一种值的情况。
- 全都是 k-1,即全是必经点,显然满足条件的只有 k=n 时 P=\{1,2,\ldots,n-1,n\}。
- 全都是 k,考虑非必经点一定是成对出现,当一对点中的一个点被删掉,另一个点能发挥等效的作用,即一对点对 LIS 产生长度为 1 的贡献,那么可得 n 个非必经点至多产生 \lfloor\dfrac{n}{2}\rfloor 的贡献,必要条件就是 k\leq \lfloor\dfrac{n}{2}\rfloor,这个序列由 2k 个非必经点和 n-2k 个无用点构成。这个条件也是充分的,考虑形如 P=\{n-k+1,n-k,\ldots n,n-2k+1,\ldots\}
接下来就只考虑 A 存在两种值的情况,分析 k 的取值范围。假设有 x 个必经点,那么会产生 x 的贡献,可得 k\geq x;非必经点也可能对 k 产生贡献,假设将必经点的位置作为切割点将整个序列分成若干段,我们发现只有同段的点才可能等效,那么可得每对非必经点都在一段内,设每段的长度为 len_i,那么至多有 \sum_i \lfloor\frac{len_i}{2}\rfloor 对非必经点,可得 k\leq x+\sum_i \lfloor\frac{len_i}{2}\rfloor。
分析出了必要条件是 x\leq k\leq x+\sum_i \lfloor\frac{len_i}{2}\rfloor。似乎分析不出更多了,那么就大胆猜测这就是充要条件(的确是充要的,如果是打比赛就可以直接开始数数了)。我们尝试通过构造方案来证明这是充分的。
设 x 个必经点分别为 b_1,b_2,\ldots,b_x,必经点和非必经点合并在一起构成 c_1,c_2,\ldots,c_m。
我们首先考虑填上无用点,考虑对于前 l 个无用点我们依次填上 \{n,n-1,\ldots,l+1,l\},对于后 r 个无用点依次填上\{r,r-1,\ldots,1\}。这样做是不合法的当且仅当 l 填到了 c_{m-1} 的后面或 r 填到了 c_2 的前面,想要满足这样必须要满足 x=2 并且不存在非必经点,这种情况下 k=2,k-1=1,但是题目要求 A_i\geq 2,所以非法的情况不存在,我们这样填一定是可以的。
之后考虑非必经点被必经点划分成了若干段((b_i,b_i+1) 对应的值域为 (a_{b_i},a_{b_{i+1}})),处理方法和上面“全都是 k ”一样,假设给第 i 段(设值域为 [l_i,r_i])分配了 k_i 个贡献,那么填上 P_i=\{r_i-k_i+1,r_i-k_i,\ldots r_i,r_i-2k_i+1,\ldots\} 即可。
于是我们证明了充分性。
之后考虑如何数这个东西,枚举必经点数量 x 和非必经点对数量 y,使用插板法然后乘上 k 的方案即可:
\sum_{x=1}^{\min\{m,n-1\}}\sum_{y=0}^{\lfloor\frac{n-x}{2}\rfloor}\binom{x+y}{y}\binom{x+1}{n-x-2y}(\min\{m,x+y\}-\max\{x,3\}+1)
code
int n,m,ans;
int C[5005][5005];
signed main(){
//file();
n=read(),m=read(),djq=read(); C[0][0]=1;
rep(i,n) C[i][0]=1;
rep(i,n) rep(j,i) C[i][j]=add(C[i-1][j-1],C[i-1][j]);
ans=min(m,n/2)-1+(m>=n-1);
rep(i,min(n-1,m))
for(rg int j=0;j*2+i<=n;++j)
if(min(i+j,m)>=max(3,i))
pls(ans,1ll*C[i+1][n-i-j*2]*C[i+j][j]%djq*(min(i+j,m)-max(3,i)+1)%djq);
printf("%d",ans);
return 0;
}