1月6日省选组总结

---

T1：mate

题目大意：

有n个点，m1条黑边，m2条白边，每个点最多有2条边，问将在n的排列中，有多少个排列满足每个点的黑边和白边的另一端点与原来一样

解法:

不难发现，对于每个连通块，可以构成简单环，链
对于长度为的环，它自己的置换有种，若有个这种环，则总数为
对于偶链,每条有种置换,所以就有
对于奇链,每条只有种置换,所以只有最后累乘一下即可

总结:

分类讨论要讨论清楚!

T2: teleport

题目大意:

有一颗个点的树,其中点到点的距离为,记每个的点的点权为,要求满足条件和

解法:

化简条件2,得到,即,发现这就是一个松弛操作,对于条件1,可以构建点0,令其为起点,那么有,也就是说,从向连的边,从向连的边,判负环即可,题解说可以用,但其常数巨大,会超时,所以我们要用求出从子树外和子树内到点的最小距离,然后就可以求解最小环了

总结:

分析时间复杂度时要考虑常数,常数太大会时超!!!

T3:tree

题目大意:

有一张个点条边的图,有三种边,问第二种边数量不超过,第三种变数量不超过的生成树数量

解法:

这道题是矩阵树定理,但是直接矩阵树定理没法做,考虑用二元拉个朗日差值求出其多项式,加速其过程

总结:

要加强知识点积累

---

---

2022年5月28日A组总结

T1：鞍点

题目大意：

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

解法：

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

总结：

存在性问题考虑容斥

T2：三角形

题目大意：

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

解法：

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

总结：

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

T3：小a的强迫症

题目大意：

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

解法：

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

总结：

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

T4：数格子

题目大意：

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

解法：

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

总结：

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