ARC160

· · 个人记录

A - Reverse and Count

考虑从前往后考虑每一位是什么。对于 i，令 j 表示目前枚举到的答案的 q_i，那么如果 j=p_i，那么满足 q_i=j 的排列个数是后面的随便 swap，或者前面的单点 swap；否则就必须从后面把 j swap 过来，只有一种方案。

复杂度 O(n ^2)。

https://atcoder.jp/contests/arc160/submissions/41416098

B - Triple Pair

考虑枚举三者之间的等价关系。有一个严格最大值的时候，数量即 3\sum_{x} \min(x-1,\lfloor\frac{N}{x}\rfloor)^2；有恰好两个最大值的时候，数量即 3\sum_{x} \min(x-1,\lfloor\frac{N}{x}\rfloor)；三个都一样，暴力枚举即可。计算式子可以整出分块。

复杂度 O(T\sqrt N)。

https://atcoder.jp/contests/arc160/submissions/41417286

C - Power Up

我们把所有操作排序，这样不同的操作可以唯一对应一个结果序列。考虑 DP。f(i,j) 表示只考虑前 i 个，满足 i 有 j 个的方案数。转移枚举 i 删多少个。\sum j 显然是 O(n\log n) 的。

复杂度 O(n\log n)。

https://atcoder.jp/contests/arc160/submissions/41418507

D - Mahjong

首先我们先进行横着删（即连续 k 个数减一），再竖着删，保证每个点作为横着删的段尾的数量 <k，那么显然我们的合法数列和删除方案是可以一一对应的。于是我们对前面那个 <k 的限制进行容斥，然后再插板，枚举横着删多少次，令 m'=m/k，可以得到

ans=\sum_{i}(-1)^{i}\binom{n-k+1}{i}\sum_j \binom{j-i+n-k}{n-k}\binom{m'-j+n-1}{n-1} = \sum_{i} (-1)^i \binom{n-k+1}{i}\binom{m'-i+2*n-k}{2*n-k}

https://atcoder.jp/contests/arc160/submissions/41422157

E - Make Biconnected

首先每个叶节点一定要连边。而叶节点为偶数的情况，在题目的 deg<3 条件下，一定存在一种方式使得它们能够匹配，且形成双连通分量：找到一个点 r，使得其三个儿子的子树中叶节点个数各不超过叶节点总数的一半，然后就可以匹配了。然后我们考虑奇数的情况，一定是会多一个点出来，然后这个点往上跳到第一个三度点形成一个路径，这个多出来的点可以与路径外的点连边形成双连通图。暴力枚举多出来的点即可。

https://atcoder.jp/contests/arc160/submissions/41434636

F - Count Sorted Arrays

首先考虑做如下转化：对于排列，由于这题中的操作只与大小有关，于是我们把它转化成一组 n 个二进制数，第 i 个二进制数表示每一位上是否大于等于 i，于是一个排列转化成 n 阶超立方体上的 (0,...,0) 到 (1,...,1) 的路径。而一个排列有序，当且仅当其所有二进制数有序，所以我们只需要维护交换对于二进制数的影响，然后再求一次路径数即可。我们可以每次求出每个二进制数是否合法，然后用它来暴力更新的话，总复杂度 O(3^n)。我们维护每个二进制数在经过这些变换之后会变成什么，然后每次 check 哪些变成了有序的状态。考虑维护集合 V(x,y) 表示 x 位置 =1，y 位置 =0 的所有二进制数，然后对于修改 x,y 就暴力找 V(x,y) 内部的点，然后暴力更新 V(x,y)。实际操作中不需要完全动态维护 V(x,y)，因为一次 x,y 操作会把 V(x,y) 清空，所以我们只需要维护加入，不用维护删除。

https://atcoder.jp/contests/arc160/submissions/41438556