传送门

结论题,可以发现每次推一个球之后,剩下的相邻两项的期望距离还是一个等差数列,所以递归下去算就行了。每次是$O(1)$的,所以总复杂度是$O(n)$的。

#include <cstdio>
#include <cstring>

long double solve(int n,long double a,long double d){
    if(!n) return 0;
    long double res=a+d*(2*n-1)/2;
    long double a1=(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n);
    long double a2=((a+d)*(2*(n-1)-1)+(a+3*d)*2+(3*a+6*d))/(2*n);
    return res+solve(n-1,a1,a2-a1);
}

int main(){
    int n;
    double a,d;
    scanf("%d%lf%lf",&n,&a,&d);
    printf("%.20lf\n",(double)solve(n,a,d));
}