卡特兰数和斯特林数

· 2025-03-11 · # 数论 # 笔记

NOI2018 冒泡排序

打表发现满足条件的序列上升的部分占绝大多部分，考虑从这个性质下手。

对于最优的情况，显然是每一步都会让两个元素都想有利于自己的方向前进，所以如果出现了长度大于等于 $3$ 的下降子序列，那么就是一定不合法的。

具体的，因为如果出现 $3$ 个以上的下降序列那么他就即需要向前走也需要向后走就不合法了，考虑用 DP 来计数。

设 $f_{i,j}$ 表示前 $i$ 个位置的最大值为 $j$ 的情况下后面 $n-i$ 个位置的方案数，容易理解 $i\le j$ 。

如果填比 $j$ 大的数，那么一定可以接在 $j$ 的后面；如果要填比 $j$ 小的数，那么必须填当前还没有填的中最小的，否则上升子序列将不止 $2$ 个，所以：

f_{i,j}=\sum\limits_{k=j}^n f_{i+1,k}

用图像表示这样的地推，那么 $f_{i,j}$ 就相当于从 $(i,j)$ 走到 $(n,n)$ 不穿过 $y=x-1$ 的方案数。

利用类似于卡特兰数的思路，我们可以得到：

f_{i,j}={2n-i-j-1\choose n-i-1}-{2n-i-j-1\choose n-j-2}

套路的，我们去枚举前缀一样的长度。

~~考虑分讨，写一个前缀和优化然后乱作即可。~~

注意到不是很显然，记录一下。

我们记 $mx$ 表示 $[1,i)$ 的 $q$ 中的 $\max$ ， $mn$ 表示还没有用过的最小的数，那么显然为了避免出现长度为 $3$ 的下降子序列，我们这个位置只能填 $\{mn\}\cup(mx,+\infty)$ 中的数。

考虑 $q_i$ 对这个位置的限制，因为我们枚举的是前缀，所以这个位置可以放的就只有 $(q_i,+\infty)$ 的数。

但是由于定义， $\nexists i\mid q_i<mn$ ，于是我们得到并集为 $(\max(mx,q_i),+\infty)$ 。

特别的，如果 $q_i\in(mn,mx)$ 那么这个位置之后就一定是不合法的，因为 $mx,q_i,mn$ 就一定构成了一个 $3$ 个元素的下降子序列，直接停止就行了。

需要考虑的问题就是答案的一堆 $f$ 加起来怎么求，注意到：

\sum\limits_{j=l}^n f_{i,l}=f_{i-1,l}

于是求和即可，时间复杂度为 $O(Tn)$ 。

容易想到，只需要保证每一行或者每一列有车就行了。

不妨设每一列都必须有车，那么如果需要有 $k$ 组车相互可以攻击，那么就只需要把 $n$ 个车放到 $n-k$ 行，每一行都至少有一个。

如果不理解，不妨继续手玩一下，那么枚举有几个空盒子容斥就行了。

Ans={n\choose n-k}\times2\sum\limits_{i=0}^{n-k} {n-k\choose i}\times(-1)^i\times(n-k-i)^n

时间复杂度为 $O(n\log n)$ 。

对于 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 有递推式子：

\begin{Bmatrix}n+1\\m\end{Bmatrix}=\begin{Bmatrix}n\\m-1\end{Bmatrix}+m\times \begin{Bmatrix}n\\m\end{Bmatrix}

那么得到：

\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\times \begin{Bmatrix}n-1\\m\end{Bmatrix}

所以在模 $2$ 意义之下就是：

\begin{Bmatrix}n\\m\end{Bmatrix}=\left\{\begin{matrix}\begin{Bmatrix}n-1\\m-1\end{Bmatrix} & m\text{ is even.} \\\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+\begin{Bmatrix}n-1\\m\end{Bmatrix} & \text{Otherwise.}\end{matrix}\right.

那么使用数形结合的思想，就相当于：

如果在位置 $(x,y)$ 那么有情况：

那么假设有 $d$ 行可以横着走，那么 $d=\lfloor\dfrac{M+1}{2}\rfloor$ 则方案数位：

{n-m+d-1\choose d-1}

所以怎么判断一个组合数的奇偶性呢，有结论只有 $n\&m=m$ 的时候 $n\choose m$ 才是奇数。