下午茶合集
10.17 767C
树上, 一次DFS求出子树的和/子树的点权和, 必须掌握的套路
无关: 可以在线跑任务的平台:
- colab google 需要科学 需要外币
- autodl 国内的 不知道收费怎么样
10.18 1420D
https://codeforces.com/problemset/problem/1420/D
输入 $n, k(1\lt k \lt n \lt 3e5)$ 和 $n$ 个闭区间，区间的范围在 $[1,1e9]$。
你需要从 $n$ 个区间中选择 $k$ 个区间，且这 $k$ 个区间的交集不为空。
输出方案数模 $998244353$ 的结果。
对这些区间排序，比如按照左端点排序
选定其中的第$i$个区间，那么在它之后的，能够交集不为空的区间的左端点 小/等于 区间$i$的右端点， 在它之前的 能够交集不为空的区间的左端点 大于/等于 区间$i$的左端点
假设给定区间$i$，左边坐标是$l$，右边是$r$，那么在$[l, r]$ 区间里面任选$k - 1$ + 选择区间$i$ 就是包含区间$i$的方案数。
去重复的问题?
看了一眼解答，是这样去重复的
考虑每个区间$i$的左端点，考虑交点为$i$区间左端点$L$的情况；
有交集的集合假设有$m$个，其中左端点等于$L$的有$x$个
那么交集包含左端点$L$的可选个数就是$c(k,m) - c(k,m - x)$个 就是去掉所有集合都不在这些里面的哪些解
把所有的区间交集取值为某个左端点，全部加起来就是答案了
组合数里面有除法，此时由于数字太大没法直接算除法，需要用乘法逆元