[atAGC055C]Weird LIS

注意到$A$中极差不超过1，不妨用二元组$(l,\{x\mid A_{x}

从$(l,S)$的角度考虑，显然限制即$l=2,S=\empty$或$3\le l\le m,S\subset [1,n]$

关于前者，可以简单构造，不难发现其总是合法的

关于后者，显然原排列LIS的长度总为$l$或$l+1$，再对其分类讨论：

1.若LIS的长度为$l+1$，即每一个元素都必然在LIS中，也即$(l,S)=(n-1,\empty)$

2.若LIS的长度为$l$，即所有必然在LIS中的元素恰构成集合$S$，此时有以下结论——

结论：记$S$中的元素依次为$pos_{1},pos_{2},...,pos_{k=|S|}$，并定义$pos_{0}=0$且$pos_{k+1}=n+1$，则合法当且仅当满足$k\le l\le k+\sum_{i=0}^{k}\lfloor\frac{pos_{i+1}-pos_{i}-1}{2}\rfloor$

必要性：左半部分显然，考虑右半部分——

对于（原排列）所有LIS，将其中第$i$个数（在排列中的位置）取并得到集合$T_{i}$

根据LIS的性质，不难得到$\forall 1\le i

对于每一个$pos_{i}$，即存在$T_{x}=\{pos_{i}\}$，代入可得$\max T_{x-1}

另一方面，除去这些$T_{x}$以外，其余$x'$必然有$|T_{x'}|\ge 2$，且必然在某两个$pos_{i}$之间，再算上本来的$k$个，总集合数至多为$k+\sum_{i=0}^{k}\lfloor\frac{pos_{i+1}-pos_{i}-1}{2}\rfloor$，显然要$\ge l$

充分性：结合上面的证明，构造形如$(2\ 1)(4\ 3)5(7\ 6)...$这样的结构，现在问题即需要处理多余的位置

具体的，在$pos_{k-2}$之前（多余的位置）填最大的若干个数，之后填最小的若干个数（均倒序），显然若选了这些位置，该上升子序列长度必然达不到$l$（可以自行分析）

考虑如何统计：枚举$S$，那么$l$的限制即$l\in \Z[\max(k,3),\min(k+\sum_{i=0}^{k}\lfloor\frac{pos_{i+1}-pos_{i}-1}{2}\rfloor,m)]$

枚举$k$和$s=\sum_{i=0}^{k}\lfloor\frac{pos_{i+1}-pos_{i}-1}{2}\rfloor$，也即可求出该式，下面考虑统计对应的$S$方案数：

设$pos_{i+1}-pos_{i}-1=2x_{i}+p_{i}$（其中$p_{i}\in \{0,1\}$?），条件也即
$$
\begin{cases}\sum_{i=0}^{k}(2x_{i}+p_{i})=\sum_{i=0}^{k}(pos_{i+1}-pos_{i}-1)=n-k\\\sum_{i=0}^{k}x_{i}=s\end{cases}
$$
结合两式，第一个条件即等价于$\sum_{i=0}^{k}p_{i}=n-k-2s$，也即两者独立

不难得到两者的方案数分别为${k+1\choose n-k-2s}{s+k\choose k}$，直接计算即可

时间复杂度为$o(n^{2})$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 10005
 4 #define ll long long
 5 int n,m,mod,ans,fac[N],inv[N];
 6 int C(int n,int m){
 7     if ((m<0)||(m>n))return 0;
 8     return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
 9 }
10 int main(){
11     scanf("%d%d%d",&n,&m,&mod);
12     fac[0]=inv[0]=inv[1]=1;
13     for(int i=1;i1]*i%mod;
14     for(int i=2;imod;
15     for(int i=1;i1]*inv[i]%mod;
16     ans=1;
17     if ((n>3)&&(m==n-1))ans++;
18     for(int k=0;k<=n;k++)
19         for(int s=0;s<=(n>>1);s++)ans=(ans+(ll)max(min(k+s,m)-max(k,3)+1,0)*C(k+1,n-k-(s<<1))%mod*C(s+k,k))%mod;
20     printf("%d\n",ans);
21     return 0;
22 }