热门标签
热门文章
- 1Linux入门之使用 dmesg 查看引导日志_dmesg日志在哪里
- 2windows环境下无法默认git运行.sh文件，选择在git中直接运行_sh脚本默认变成git的图标了
- 3STM32发生HardFault_Handler错误的查找方法_hardfault_handler的上一步
- 4R语言数据可视化之图形参数修改_图形参数"pin"的值设得不对
- 5bat文件批量打开应用程序/快捷方式_批量打开软件批处理
- 6使用virt-install手动创建qcow2镜像并安装ISO_virt-manager找不到本地镜像
- 7【服务器数据恢复】DELL Eq PS系列服务器硬盘坏道的数据恢复案例_eqps
- 8R语言ggplot2中的theme函数_r语言theme函数
- 9【半月刊 4】前端高频面试题及答案汇总
- 10【浅谈MySQL数据目录】Ubuntu安装Mysql8服务器，相关数据目录介绍_ubuntu18.04安装mysql8时指定数据目录
当前位置: article > 正文
2020 ICPC Macau A. Accelerator（期望，计数，分治FFT）（每日一题 21.7.6）
作者：你好赵伟 | 2024-02-10 18:44:21
赞
踩
2020 ICPC Macau A. Accelerator（期望，计数，分治FFT）（每日一题 21.7.6）
整理的算法模板合集： ACM模板
实际上是一个全新的精炼模板整合计划
2020 ICPC Macau A. Accelerator（分治FFT）
Problem
给定长度为 n n n 的数组 a i a_i ai ，对于 1 ∼ n 1\sim n 1∼n 的所有的排列 p i p_i pi ，计算 ( ( ( ( 0 + 1 ) ∗ a p 1 + 1 ) ∗ a p 2 + ⋯ ) + 1 ) ∗ a p n ((((0 + 1) *a_{p_1} + 1) * a_{p_2} + \cdots) + 1) * a_{p_n} ((((0+1)∗ap1+1)∗ap2+⋯)+1)∗apn 的期望。
n ≤ 1 0 5 n\le 10^5 n≤105
Solution
显然我们把要求的式子展开以后有：
v a l = ∏ i = 1 n a p i + ∏ i = 2 n a p i + ⋯ + ∏ i = n n a p i val = \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} val=i=1∏napi+i=2∏napi+⋯+i=n∏napi
推荐阅读
相关标签
