---

---

2022年5月28日A组总结

T1：鞍点

题目大意：

对于一个的矩阵，统计至少有一个鞍点（第行列的严格最大值）的矩阵个数

解法：

我们考虑钦定鞍点数量，然后进行一个容斥
设原来有个鞍点，最大值为 ，我们如果加入个值为的鞍点，那么我们首先要确定鞍点的位置，有种，由于有顺序，所以公种方案，其中有是新填的数，所以

总结：

存在性问题考虑容斥

T2：三角形

题目大意：

对于平面点集{}我们要添加一个点，使得新的点集的有直角边平行与坐标轴的Rt三角形数量最多

解法：

我们可以线性预处理原来的答案，然后就得到了一个式子
考虑到时越大越优， 时越大越优，我们可以预处理每个的最大的，优因为所以最多有种，枚举即可

总结：

有时考虑去重后的数量可以大大优化算法复杂度

T3：小a的强迫症

题目大意：

有n种珠子，第种的最后一个一定要在第种之前，求方案数

解法：

我们先让每种珠子放好了最后一个，那么第种珠子前面一共有个珠子，所以共有种方法，累积即可

总结：

虽然方案数常用dp做，但加乘原理不能忘记

T4：数格子

题目大意：

求用多米诺骨牌摆满一个的矩形的方案数

解法：

我们发现，行与行之间的转移很相像，于是可以直接矩阵乘法

总结：

轮廓线DP的部分分，逐行dp和逐格dp需要斟酌