bzoj 2698: 染色

题意：

有$n$个格子排成一排。初始时，所有格子都是黑色的。现在进行$m$次染色操作，每一次会随机选取一段长度在$[s, t]$之间的连续段染成白色。求最后被染成白色的格子个数的期望值。

题解：

先要知道一点：答案就是每个格子染成白色的概率加起来。（感觉一下挺对的）那一个最终被染白的概率就是$1 - (1 - p) ^ m$，其中$p$表示一次被染白的概率。问题就在如何求每个位置的$p$上。我们可以从左往右扫过去，维护一下有多少个区间会覆盖当前的$i$。具体来说就是当$i$变为$i + 1$时，以$i$为右端点的区间要删除，以$i + 1$为左端点的区间会加入。随便搞搞就好。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m, s, t;
double ans = 0;

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    long long tot = 1LL * (2 * n + 2 - s - t) * (1 + t - s) / 2, now = t - s + 1;
    for (int i = 1; i <= n; i++)
    {
        ans += pow(1 - 1.0 * now / tot, m);
        now = now - max(0, min(i, t) - s + 1) + max(0, min(n - i, t) - s + 1);
    }
    printf("%.3lf\n", n - ans);
}