传送门
题解：
利用期望公式：
E[max{S}]=∑T∈S(−1)|T|+1E[min{T}] E [ max { S } ] = ∑ T ∈ S ( − 1 ) | T | + 1 E [ min { T } ] 我们对于每个子集算期望， 容易知道为 n∗(n+1)2sum n ∗ ( n + 1 ) 2 s u m ， sum s u m 为包含子集任意一个点的区间的个数。补集转化，统计不经过的，只有相邻的两个子集中的球内部的区域有效。 上界为 n2 n 2 个，我们DP即可。
这个式子怎么来的呢，其推导如下： 不妨记第 i i 次把区间全部染黑的概率为pipi，那么：
E[X]=∑i=0∞i∗pi E [ X ] = ∑ i = 0 ∞ i ∗ p i 等价于 E[X]=∑i=0∞[X>i] E [ X ] = ∑ i = 0 ∞ [ X > i ] 因为一种情况刚好被算了相同的次数。 考虑如何求 P[X>i] P [ X > i ] ，我们枚举 2n 2 n 个集合表示 i i 步后哪些没有被染黑，那么显然之前的ii步只能选不包含集合中点的区间。 因为会算重，我们用组合数： ∑ni=1(−1)i−1(ni)=[n>0] ∑ i = 1 n ( − 1 ) i − 1 ( n i ) = [ n > 0 ] 来容斥即可。我们发现枚举 i i 的每个子集，计算概率时唯一变化的是pipi，这是一个等比数列，最终贡献为 11−p 1 1 − p 。
那么答案就为
∑T∈S(−1)|T|−111−p=∑T∈S(−1)|T|+1E[min{T}] ∑ T ∈ S ( − 1 ) | T | − 1 1 1 − p = ∑ T ∈ S ( − 1 ) | T | + 1 E [ min { T } ] （因为 1−p 1 − p 就是选到的概率，也就是 minT min T ）本机是对的但是交到HDU老爷机上WA了，最后直接打表了。
#include <bits/stdc++.h> #include <decimal/decimal> using namespace std; typedef long long LL; typedef __float128 DB; #define P(x) ((x)*(x+1)/2) const int N=55; LL f[N][P(N)][2]; inline void pre() { f[0][0][0]=1; for(int i=1;i<=51;i++) for(int j=0;j<=P(i);++j) for(int pre=0;pre<i;++pre) if(P(i-pre-1)<=j) f[i][j][0]+=f[pre][j-P(i-pre-1)][1], f[i][j][1]+=f[pre][j-P(i-pre-1)][0]; } int main() { pre(); for(int n=1;n<=50;n++) { DB ans=0; for(int j=0;j<P(n);++j) ans+=DB((f[n+1][j][0]-f[n+1][j][1])*P(n))/(P(n)-j); } const string ans[51]={"0","1.000000000000000","2.000000000000000","2.900000000000000","3.742063492063492","4.550782550782551","5.339458438877944","6.115568709170809","6.883515849207354","7.646001329298163","8.404742484047103","9.160864322251938","9.915122959697986","10.668037886196054","11.419972864667116","12.171186847949863","12.921866842501495","13.672149598205217","14.422136210550637","15.171902127505054","15.921504117722232","16.670985193367588","17.420378133764190","18.169708037741841","18.918994192607536","19.668251456354044","20.417491289207981","21.166722529914919","21.915951984406581","22.665184875333577","23.414425187561400","24.163675935274249","24.912939369587052","25.662217140708672","26.411510425169478","27.160820026039890","27.910146452156218","28.659489980948755","29.408850708402174","30.158228588875146","30.907623466896614","31.657035102590944","32.406463192027060","33.155907383511126","33.905367290628666","34.654842502675537","35.404332592986861","36.153837125570658","36.903355660372082","37.652887757430200","38.402432980138351"}; int T; cin>>T; while(T--) { int n; cin>>n; cout<<ans[n]<<endl; } }