1 条题解
-
2
观察到所有互不相同的歌曲对答案的贡献独立,于是我们逐歌曲类型考虑。
假设当前类型出现位置为 。我们计算有多少个 使得 包含至少一个 ,和有多少个使得 包含至少一个 。
对于 :
定义 为对所有左端点在 ,右端点在 的区间的子区间数量和。则:
$$c(X,Y)=\sum_{i=1}^X\sum_{j=1}^Y\binom{i+j}{2}=\sum_{i=1}^X\sum_{j=1}^Yij+\binom i2+\binom j2 $$$$=(\sum_{i=1}^Xi)(\sum_{j=1}^Yj)+Y(\sum_{i=1}^X\binom{i}{2})+X(\sum_{j=1}^Y\binom{j}{2}) $$将这些和预处理即可。
枚举 里的第一个 ,固定为 ,则有 个 满足 包含 。
最后,如果这个歌曲编号是 ,将累计起来的贡献乘 即可得到总共 方案数。
对于 :
现在我们根本不可能用 了,因为可行的 数量依赖于位置。
定义 为 数量,使得 包含 并且 左端点大于等于 。第一发现 和 右端点不受任何限制也和左端点独立,枚举 到 右端点之间的可能左端点数量得到 可行右端点数量为通项即可。我们再枚举 左端点的位置, 必须在 左端点左边,于是左端点数量为
通项即可。按照第一部分一样方法处理。
所有类型贡献加起来得到答案,时间复杂度 。
- 1
信息
- ID
- 163
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 29
- 已通过
- 3
- 上传者