AGC055C

· · 题解

solution

考虑寻求存在满足条件的排列 P 的充要的条件。

首先显然的是假设整个序列的 LIS 长度为 k，那么 A_i\in\{k-1,k\}，因为去掉一个 LIS 里的数之后剩下的 k-1 个数仍然构成 LIS，长度至少为 k-1，并且还可能去掉后无影响即长度为 k。

下面定义必经点、非必经点、无用点。

  1. 若位置 i 在所有 LIS 中，即去掉位置 i 后 LIS 长度减少，那么称 i 为必经点，有 A_i=k-1。
  2. 若位置 i 在某个 LIS 中，且去掉位置 i 后 LIS 长度不变，那么称 i 为非必经点，有 A_i=k。
  3. 若位置 i 不在任何一个 LIS 中，那么称 i 为无用点，有 A_i=k。

首先我们考虑整个 A 序列都是一种值的情况。

  1. 全都是 k-1，即全是必经点，显然满足条件的只有 k=n 时 P=\{1,2,\ldots,n-1,n\}。
  2. 全都是 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;
}