/problem/CF1267G
麻了，回头看的时候一下子不会算贡献了
白写了可还行
首先考虑抽卡的期望，假设已经抽了 i i i个圣遗物出来，要出 i + 1 i+1 i+1个圣遗物的期望是
E ( i ) = i n ( E ( i ) + x 2 ) + n − i n × ( x + E ( i + 1 ) ) E(i)=\frac{i}{n}(E(i)+\frac{x}{2})+\frac{n-i}{n}\times(x+E(i+1)) E(i)=ni(E(i)+2x)+nn−i×(x+E(i+1))
E ( i ) − E ( i + 1 ) = ( n n − i + 1 ) × x 2 E(i)-E(i+1)=(\frac{n}{n-i}+1)\times \frac{x}{2} E(i)−E(i+1)=(n−in+1)×2x
有个重要的性质：先抽卡后买
应为对于当前状态，假设最优选择是抽卡，如果抽卡啥也没有得到，那么状态不会变，继续抽如果开始买了，说明 剩 下 的 n − i < x 2 ( n n − i + 1 ) \frac{剩下的}{n-i} < \frac{x}{2}(\frac{n}{n-i}+1) n−i剩下的<2x(n−in+1),买了一个后，右边的期望会变大，左边的因为分母 − 1 -1 −1，分子至少 − 1 -1 −1,所以会变得更小, 所以会一直买
考虑dp，设 f [ i ] [ j ] f[i][j] f[i][j]表示得到了 i i i个圣遗物，价格和为 j j j的概率
并不好算，可以考虑算方案数，然后再 / ( n i ) /\binom{n}{i} /(in)
然后枚举所有的情况，用权值 * 概率求个和即可
code:
#include<bits/stdc++.h>#define N 105#define M 1005#define db doubleusing namespace std;db c[N][N], f[N][M];void init(int n) {for(int i = 0; i <= n; i ++) c[i][0] = 1;for(int i = 1; i <= n; i ++)for(int j = 1; j <= i; j ++)c[i][j] = c[i - 1][j] + c[i - 1][j - 1];}int n, x, a[N], m;int main() {scanf("%d%d", &n, &x);init(n);for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);f[0][0] = 1;for(int i = 1; i <= n; i ++) {m += a[i];for(int j = n; j >= 1; j --) {for(int k = m; k >= a[i]; k --)f[j][k] += f[j - 1][k - a[i]];}}db ans = 0;for(int i = 0; i < n; i ++) {for(int j = 0; j <= m; j ++) {ans += f[i][j] / c[n][i] * min((m - j) * 1.0 / (n - i), (n * 1.0 / (n - i) + 1) * (x / 2.0));}}printf("%.14lf", ans);return 0;}
