CF1842

考虑钦定根节点为黑点重心，这样选每个点为黑点对答案造成的贡献是独立的。

如果计算答案时当前点不是黑点重心，那么会使答案更小，不会产生影响。

于是可以枚举黑点重心，

O(n^2 \log n)

解决本问题，瓶颈在于排序。

非常神秘，考虑乘法分配率的每条路径，每次从

a_i

转移到

a_{i+1}

时。

设

f_{i,j}

表示长度为

i

的前缀，钦定了

j

个操作的答案。

f_{i,j}(a_i+jv) \rightarrow f_{i+1,j}

f_{i,j}(m-j)iv\rightarrow f_{i+1,j+1}

答案为：

\frac{\sum_{j=0}^{m}f_{n,j}n^{m-j}}{n^m}

神秘 trick 题，有点过于人类智慧了。

首先设

y_i = x_i - 0.5

，条件转化为

y_i + y_j \le 0

或

y_i + y_j \ge 0

，这个式子只和绝对值较大的

y

有关。

因此我们状压 dp，钦定新加入的

y

绝对值更大，容易做到

O(2^nn)

。

文章操作