奥义商店

from BZOJ NOI十连测 R1T1

题目大意:给定个物品,每个物品的价格是,同时给定种颜色,给定一个下标,和一个方差,让你给所有物品染色,每种颜色必须染个,同时第个物品可以染任意一种(不包括在内),即。求包含的与同色的、下标与构成等差数列且方差为的期望花费(),同时支持单点修改的值。

3 3 1 1 1 2 2 1 1 1 1//2 t k d接下来t个整数表示 1 2 2//1 x y表示将修改为 2 2 3 1 1 1

1.5000 2.0000

考虑的做法,对于一个点的期望值可推得(这里以右半部分为例,注意左右被选概率相等,对于一个点Q为等差数列上的点,令为最小的)为,就可以用期望的线性性质求解。

看题目,由于题目只要求到小数点后4位,当上面的里的逐渐增大,连乘的结果会以指数级递减。

故当时就没必要继续进行下去。(:不一定必须要是100)。

Code: