020f
AGC020F Arcs on a Circle
一个和值域无关的算法,复杂度 \(O(4^nn^2)\),不过好像可以用子集卷积和拉格朗日插值优化至 \(O(3^nn^3)\)。 如果说原问题在整数上做,我们通常可以用生成函数来刻画容斥的式子,求个二维 \(\exp\) 状物就可以了,但是在实数域似乎不太好扩展,但实际上是可以扩展的。 原问题实际 ......
[AGC020F] Arcs on a Circle 题解
Arcs on a Circle 首先,一个非常自然的想法是尝试断环成链。怎么断呢?我们发现,选择最长线段的起点处截断是个非常好的选择,因为不可能有一个线段完全覆盖它。这之后,一个紧接着的想法就是 DP。 假如把描述中的全部“实点”改成“整点”的话,那么这题是比较 trivial 的,可以通过随便状 ......
AGC020F Arcs on a Circle
先考虑只能放**整点**的情况,不难想到考虑 dp。 对于环上的 dp,考虑**断环成链**,即钦定一条线段的左端点为**起点**。这里我们令长度**最长**的线段的左端点为环的起点。 这样做有一个好处:我们不用考虑**一条线段把环末尾覆盖再覆盖开头的空**的情况,而当我们钦定一个长度较小的线段作为 ......