题目

输入：N, K, W
输出：从0点开始每次增加[1, W]的随机数，直到大于等于K点。问最终点数小于等于N的概率。

符号定义：

A[start, end) = A[start] + A[start+1] + ... + A[end - 1]
A[start, end] = A[start] + A[start+1] + ... + A[end]

一、用过去推现在

定义P[k]为不限抽取次数，获得k点的概率。
则P[k] = (P[k-1] + P[k-2] + ... + P[k-W])/W 简写作P[k-W, k) / W
只需快速求出P[k-W, k)，就可计算P[k]。同时记得区间[k-W, k)不能超出区间[0, K)，因为点数大于等于K时无法继续抽取。

方法1：前缀和数组

定义P的前缀和数组：SumP[k] = P[0, k)
则P[start, end) = SumP[end] - SumP[start]

方法2：区间累加

维护一个变量Sum，使其值保持为P[k-W, k)

二、用现在推未来

定义P[k]为不限抽取次数，获得k点的概率。
则只要k < K，就可以继续抽取，此时P[k+1], P[k+2], ..., P[k+W]的概率都要增加P[k]/W。

方法3：差分数组（化区间修改为点修改）

定义差分数组A[i]表示P[i], P[i+1], P[i+2], ...全部都加上A[i]。
则，P[k+1, k+W] += X 可简化为 A[k+1] += X 和 A[k+W+1] -= X。
此时P[k]受A[0], A[1], ..., A[k]的影响，即P[k] = A[0, k]。

代码

前缀和

double F1(int N, int K, int W){
    vector<double> P(K + W, 0.0);
    vector<double> SumP(K + W + 1, 0.0);
    P[0] = 1.0; 
    SumP[0] = 0.0;// SumP[k] = sum of P[0, k)

    for(int i = 1 ; i < K + W ; ++i){
        //更新SumP[i]
        SumP[i] += SumP[i-1] + P[i-1];

        // 求区间[i-W, i-1]的和
        int start = max(i - W, 0);
        int end = min(i, K);
        // P[start, end) = SumP[end] - SumP[start];
        P[i] = (SumP[end] - SumP[start]) / W;
    }
    //累加答案 
    double ANS = 0.0;
    for(int i = K ; i < K + W ; ++i)
        if(i <= N)
            ANS += P[i];
        else
            break;
    return ANS;
}

区间累加

double F2(int N, int K, int W){
    vector<double> P(K + W, 0.0);
    P[0] = 1.0;
    double Sum = 0.0;
    for(int i = 1 ; i < K + W ; ++i){
        // 将Sum调整为[i-W, i-1]的和
        Sum += i - 1 < K ? P[i-1] : 0.0;
        Sum -= i-W-1 >= 0 ? P[i-W-1] : 0.0;

        // 更新P[i]
        P[i] = Sum / W;
    }
    //累加答案
    double ANS = 0.0;
    for(int i = K ; i < K + W ; ++i)
        if(i <= N)
            ANS += P[i];
        else
            break;
    return ANS;
}

差分数组

double F3(int N, int K, int W){
    vector<double> A(K + W + 1, 0.0);
    // 以下两句等价于P[0] = 1.0
    A[0] = 1.0;
    A[1] = -1.0;
    double Pi = 0.0;

    for(int i = 0 ; i < K ; ++i){
        // 求P[i] = A[0, i]
        Pi += A[i];
        // 使区间P[i+1, i+W+1]都加上P[i]/W
        A[i+1] += Pi / W;
        A[i+W+1] -= Pi / W;
    }
    // 累加答案
    double ANS = 0.0;
    for(int i = K ; i < K + W ; ++i){
        Pi += A[i];
        if(i <= N)
            ANS += Pi;
        else
            break;
    }
    return ANS;
}