【VP 记录】ABC217

· · 个人记录

C.Inverse of Permutation

红题，略过不表。

D.Cutting Woods

赛时过了，但是用了离散化+树状数组写了近一个小时，然而set+二分非常简单，所以还得多练练set和multiset之类的stl，也尽量别把简单问题想复杂了。

E.Sorting Queries

赛时做了大约十分钟，使用一个队列和一个小根堆维护即可，不再赘述。

F.Make Pair

组合计数+区间dp，赛后我看题解用了另一种方法：

设 f_{l,r,0} 为 l 和 r 匹配时区间 l,r 的方案数；f_{l,r,1} 为 l 和 r 不匹配，即该区间可分成多个区间时区间 l,r 的方案数。

边界即为对于所有可匹配的 i,i+1 有 f_{i,i+1,0}=1

显然若 l,r 可匹配则 f_{l,r,0}=f_{l+1,r-1,0}，否则 f_{l,r,0}=0

而 f_{l,r,1} 的计算需要枚举中断点 k，若按乘法原理，答案为 (f_{l,k,0}+f_{l,k,1})\times (f_{k+1,r,0}+f_{k+1,r,1})。

但由于这样枚举会出现重复，在这里强制其中一段区间不可拆分来去重，因此变为 (f_{l,k,0}+f_{l,k,1})\times f_{k+1,r,0}。

然后由于方案与顺序有关，则中断点两侧还可以改变顺序，因此上面的式子还要乘上 \binom{\frac{k-l+1}{2}}{\frac{r-l+1}{2}}，即在所有位置中选择若干个给左边部分的方案数。

最后还要注意由于成对选取，枚举区间和中断点时只需枚举偶数长度即可。

G.Groups

还是组合计数。

这题有三种做法，目前还不会二项式反演。

其中最简单的一种如下：

设 f_{i,j} 为把前 i 个数放到恰好 j 个组中的方案数，则放第 i 个数时可以新开一组，也可以放到已有的组内。显然已放的与 i 模 m 同余的数个数为 \lfloor \frac{i-1}{m} \rfloor，于是可放的组就会减少这么些，若没有可放组则这种可能为 0。

如上，f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\times max(0,j-\lfloor \frac{i-1}{m} \rfloor)

边界为 f_{0,0}=1

总之FG这种考察思维的组合计数题目还得多加练习才行。