2020 ICPC Macau A. Accelerator（期望，计数，分治FFT）（每日一题 21.7.6）

作者：你好赵伟 | 2024-02-10 18:44:21

踩

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

Problem

给定长度为 $n$ 的数组 $a_i$ ，对于 $1\sim n$ 的所有的排列 $p_i$ ，计算 $*a_{p_1} + 1) * a_{p_2} + \cdots) + 1) * a_{p_n}$ 的期望。

$n\le 10^5$

Solution

显然我们把要求的式子展开以后有：

$\prod\limits_{i = 1}^{n}a_{p_i} + \prod\limits_{i = 2}^{n}a_{p_i} + \cdots + \prod\limits_{i = n}^{n}a_{p_i}$

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】