本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-05 21:15:51

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这种考察思维的组合计数题目还得多加练习才行。