典型的反转 ，整理一下此类题思路。 题意简述 你现在要按照如下方式生成一个长度为 的数组： 对于 ，有 的概率设 ，有 的概率设 。 对于一个长度为 的数组，计算 。特别地，。此时 数组的最大前缀和 。现在给定 个正整数 。该数组最大前缀和为 时，该数组的分数为 。 要求对于所有 ，求出生成出的数组的期望分数对 取模的结果。 。 思路分析 正向考虑困...

题意简述 给定 个城市，第 个城市收集到了高度为 的水，要求通过使用 次地下连通系统，每次使用可以使若干个城市的水箱相连通，然后使它们的水位变为它们的平均值。要求求出 次操作后， 号城市水箱中的水位的最大值。 策略选择及最优性证明 引理0：我们一定不会对初始水位不高于 号的水箱操作，操作与操作之间选择的水箱一定不会有重叠。 证明：显然。 引理1：对于初始水位...