洛谷4609 [FJOI2016]建筑师
Luogu LOJ 分析 显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。 除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。 于是答案为 代码 // ===================...
Luogu LOJ 分析 显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。 除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。 于是答案为 代码 // ===================...
CodeForces 分析 可以发现每种权值的贡献是一样的，我们只要求出这个系数就好了。 注意到贡献的式子里有一个 $|S|$ 。我们可以认为集合中的每个元素对答案都有一次贡献。 于是枚举每一对数的贡献即可。 $i$ 对自身的贡献显然为 $S_n^k$ 。 当 $j\neq i$ 时，贡献为 $S_{n-1}^k$ 。 于是总的系数就是 $S_n^k+(n-1)\times S_{n-1}^...