题目描述
输入
输入一行四个整数，分别为N、M、S和T。
输出
输出一行为期望值，保留3位小数。
样例输入
5 1 2 3
样例输出
2.429
题解
期望
由于期望在任何时候都是可加的，因此只要算出每个格子被染色的概率，加起来即为答案。
单次染色一个格子不被染的概率为 不经过它的区间个数/总区间个数 ，这个可以分左右部分加起来求。
然而貌似只有我丧心病狂的写了分类讨论= =
对于每个概率快速幂一下即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long double ld;
ld pow(ld x , int y)
{
ld ans = 1;
while(y)
{
if(y & 1) ans = ans * x;
x = x * x , y >>= 1;
}
return ans;
}
int main()
{
int n , m , s , t , l , r , i;
ld ans = 0 , a , c;
scanf("%d%d%d%d" , &n , &m , &s , &t) , a = (ld)(2 * n + 2 - s - t) * (t - s + 1) / 2;
for(i = 1 ; i <= n ; i ++ )
{
l = i , r = n - i + 1;
if(l >= t)
{
if(r >= t) c = (ld)(s + t) * (t - s + 1) / 2;
else if(r >= s) c = (ld)r * (t - r) + (ld)(s + r) * (r - s + 1) / 2;
else c = (ld)r * (t - s + 1);
}
else if(l >= s)
{
if(r >= t) c = (ld)l * (t - l) + (ld)(s + l) * (l - s + 1) / 2;
else if(r >= s)
{
if(l >= r) c = (ld)(l + 2 * r - t) * (t - l + 1) / 2 + (ld)r * (l - r) + (ld)(s + r - 1) * (r - s) / 2;
else c = (ld)(r + 2 * l - t) * (t - r + 1) / 2 + (ld)l * (r - l) + (ld)(s + l - 1) * (l - s) / 2;
}
else c = (ld)(l + 2 * r - t) * (t - l + 1) / 2 + (ld)r * (l - s);
}
else
{
if(r >= t) c = (ld)l * (t - s + 1);
else if(r >= s) c = (ld)(2 * l + r - t) * (t - r + 1) / 2 + (ld)l * (r - s);
else c = (ld)(2 * l + 2 * r - s - t) * (t - s + 1) / 2;
}
ans += 1 - pow(1 - c / a , m);
}
printf("%.3Lf" , ans);
return 0;
}