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$ 的方案数。

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

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

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

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

CF1342E Placing Rooks

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

不妨设每一列都必须有车，那么如果需要有 $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)$。

SP106 Binary Stirling Numbers

对于 $\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)$ 那么有情况：

• 如果 $y$ 是奇数那么只能从 $(x-1,y-1)$ 转移过来。
• 否则可以从 $(x-1,y)$ 或者 $(x-1,y-1)$ 转移过来。

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

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

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