ARC186
不打好亏！
ARC186A
打表猜个结论就过了，结论是若存在序列 $a[1,k],b[1,k]$ 满足 $\forall i\in[1,k],a_i,b_i\geq 2$ 且 $\sum a,\sum b\leq n$，则 $n^2-\sum_{i}a_ib_i$ 合法。大概就是很多个行列不交的矩形，然后矩形内部都是不固定的。
官解：建一个 $2n$ 个点的有向二分图，若 $a_{i,j}=1$ 则连边 $l_i\rightarrow r_j$，否则连边 $r_i\rightarrow l_j$。感觉有点反人类了。
考虑两个相似的矩阵，则两个图的每个点的入度和出度都相同。删去同向的边之后，因为所有点的入度和出度相等，所以图会形成若干个环。所以一个边不固定的条件就是他在一个强连通分量里。这样就可以直接 DP 了，复杂度 $\mathcal O(\frac{n^6}{w})$。
ARC186B
给定了一个数前面比他大的第一个数。首先区间的交要么为 $1$，要么为 $0$，要么包含。
考虑连边 $a_i\rightarrow i$，则形成了一个树形结构。考虑一个 $i$ 的所有儿子，从小到大排序，则应当满足填的值递增。
在上面树的基础上再建一棵树：多个儿子则前一个儿子连向后一个儿子，最后一个儿子连向自己，这个树的拓扑序数量就是答案。
ARC186C
感觉比 B 简单？
花费大于体积的所有盒子没有用，可以删掉。考虑如果确定了用哪些盒子，则 Alice 的策略是怎么样的。
首先 Alice 给过来一个球，Bob 会把他放到最大的盒子里。然后 Alice 此时显然给不同颜色的球是更优秀的，这样直到占满 $m$ 个盒子。
然后 Alice 没有新的球了，这种情况下他一定会选当前占的盒子体积最小的颜色，不断给这种球，直到占满这个盒子，然后 Bob 再新开一个盒子放这个球。
容易发现最优策略下 Bob 一定是最大的 $m-1$ 个盒子里面放了一个球（颜色两两不同），然后剩下的盒子全部放满。
所以做法就是取出所有价值小于体积的盒子，按照体积从大到小排序，枚举一个前缀，在这个前缀里面花费 $m-1$ 次代价并不获得收益，后面的盒子一定全用了，求一下最大值。拿一个堆维护代价的前 $m-1$ 小即可，复杂度 $\mathcal O(n\log n)$。
ARC186D
拜谢科技哥 $\mathrm{\color{black}{d}\color{red}{efinieren}}$。
枚举第一位不同的，那就是要求 $k$ 段波兰表达式，长度总和为 $n$ 的方案数。
设波兰表达式的生成函数是 $F(x)$，可以得到：
\[\begin{aligned} F(x)&=\frac{x}{1-F(x)}\\ F^2(x)-F(x)+x&=0\\ \end{aligned}\]暴力套用求根公式可以得
\[F(x)=\frac{1\pm\sqrt{1-4x}}{2}\]应当满足 $[x^0]F(x)=0$，所以应当取负号。但是因为需要球 $F^k(x)$，所以可能做不大了。
考虑拉格朗日反演，因为 $x=F(x)(1-F(x))$，显然 $F(x)$ 的复合逆 $G(x)$ 是 $G(x)=x(1-x)$。套用拉格朗日反演公式：
\[[x^n]H(F(x))=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n\]取 $H(x)=x^k$ 可得：
\[\begin{aligned} [x^n]F^k(x)&=\frac{1}{n}[x^{n-1}]kx^{k-1}(\frac{x}{G(x)})^n\\ &=\frac{k}{n}[x^{n-k}]\frac{1}{(1-x)^n}\\ &=\frac k n\binom{n-1+n-k}{n-1} \end{aligned}\]设 $f(n,m)=\frac k n\binom{n-1+n-k}{n-1}$，答案就是：
\[\sum_{i=1}^n \sum_{j<a_i}f(n-i,\sum_{k<i}(a_k-1)-1+j)\]因为每次 $m$ 是先减少 $1$，然后再增加 $a_i$，并且如果 $m>n$ 了那式子的答案就是 $0$，所以可以均摊直接算，如果 $m>n$ 了就直接跳出循环，每次势能增加一，所以复杂度是 $\mathcal O(n)$。
ARC186E
做题还是太慢了，做了快一个半点。这种就算会做场上也写不出来啊/fn/fn/fn。
考虑生成的序列如果合法应当满足什么条件。进行归纳，先考虑 $x_1$ 的限制。
首先设 $p$ 表示 $[1,K]$ 中的数在 $A$ 中第一次出现位置的最大值。则应当满足 $a_p=x_1$。
反证法：假设 $a_p=v,v\not=x_1$ 是 $v_1$ 出现的第一个位置则应当满足 $X[2,m]$ 不为 $A[p+1,n]$ 的子序列。但是要保证所有其他长度为 $m$ 的序列都是 $A[1,n]$ 的子序列，所以应当满足 $v$ 第一次在 $A$ 中出现位置 $p$ 的后面出现所有长度为 $m-1$ 的序列，与假设矛盾。
然后考虑如果 $x_2=x_1$，则需要 $A[p+1,n]$ 中不出现 $X[2,m]$ 并且出现其他所有长度为 $m-1$ 的序列。设 $S$ 表示全集 $\{1,2\dots K\}$，则 $S,S\setminus\{x_1\},S\dots S$ 已经在序列中出现过了，只需要保证 $S\setminus \{x_1\},x_1,S\dots S$ 出现，容易发现上面已经满足了这条限制。
如果 $x_2\not=x_1$，则需要 $A[p+1,n]$ 中不出现 $X[2,m]$ 并且出现其他所有长度为 $m-1$ 的序列。此时仍然是 $S,S\setminus\{x_2\},S\dots S$ 已经在序列中出现过了，还需要满足出现的序列是 $S\setminus\{x_1\},x_2,S\dots S$。考虑 $x_2$ 在 $p$ 前的最后一次出现位置 $q$，则应当满足 $[1,q-1]$ 出现了 $S\setminus \{x_1\}$ 的所有数。证明同上，依然使用反证法即可。
这样就可以考虑 DP 了，设 $f_{i,j}$ 表示，当前考虑了 $A$ 的前缀 $i$，出现了 $X[1,j]$。向后转移一位，分 $x_{j+1}$ 和 $x_{j+2}$ 是否相等讨论一下即可：
\[\begin{aligned} f_{i+x,j+1}&\overset +\leftarrow f_{i,j}S_{x-1,k-1}(k-1)!\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; a_{j+1}=a_{j+2}\\ f_{i+x,j+1}&\overset +\leftarrow f_{i,j}\sum_{p<x}S_{p-1,k-1}(k-1)!(k-1)^{x-1-p}\;\;\;\;\;\;\;\; a_{j+1}\not=a_{j+2} \end{aligned}\]其中 $S_{i,j}$ 表示第二类斯特林数。预处理转移系数即可做到 $\mathcal O(n^3)$。