题解

思路

设喜欢图片初始权值和为 $P$，不喜欢图片初始权值和为 $N$。进行了 $t$ 次访问、其中 $x$ 次展示喜欢图片时，两组当前总权值分别为 $P+x$ 与 $N-(t-x)$，总权值为 $P+N+2x-t$。因此下一次访问属于哪一组只与 $(t,x)$ 有关。

做法

小数据枚举所有访问序列并累积其概率。

中档算法对每张图片分别做概率 DP，除 $x$ 外再记录该图片自身被展示的次数 $z$，分别转移到该图片、同组其他图片和另一组，直接求该图片最终期望。

满分算法只维护 $dp[t][x]$。转移概率为

$$\frac{P+x}{P+N+2x-t},\qquad \frac{N-(t-x)}{P+N+2x-t}.$$

求出喜欢图片被展示次数的期望 $E[X]$。组内过程具有交换性：喜欢图片 $i$ 的期望为

$$w_i\frac{P+E[X]}P,$$

不喜欢图片 $i$ 的期望为

$$w_i\frac{N-(m-E[X])}N.$$

复杂度

满分算法时间复杂度 $O(m^2+n)$，空间复杂度 $O(m)$。