牛客NOIP暑期七天营-普及组2-C硬币

题目大意：有n枚硬币，a枚正面朝上，b枚反面朝上，每次操作随机抽取一枚翻过来，m次操作正面朝上的数量的数学期望是多少？

如果只有1枚硬币，每次翻转的都是同一枚，最终要么是正面朝上，要么是反面朝上，数学期望是0或者1。

对于n枚硬币，a枚正面朝上，b枚反面朝上，下一次有两种状态：

1、随机抽到正面朝上，翻转后a-1枚朝上，b+1枚朝下，概率是a/n

2、随机抽到反面朝上，翻转后a+1枚朝上，b+1枚朝下，概率是b/n

如果当前的情况的概率是x，那么这两种情况的概率分别是和。

反向推也是同样的道理。

递推关系：f[i][j]表示第i次操作，有j枚硬币正面朝上，上一步是f[i-1][j-1]和f[i-1][j+1]，注意边界即可。

最终答案：m次之后，1的概率+2的概率+...+n的概率。

滚动数组优化：

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b, p;
double f[5][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=1; i<=m; i++){
        for(j=0; j<=n; j++){
            f[i&1][j] = 0;
            if(j < n) f[i&1][j] += f[i-1&1][j+1] * (j+1) / n;
            if(j) f[i&1][j] += f[i-1&1][j-1] * (n-j+1) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m&1][i];
    printf("%.8lf\n", ans);
    return 0;
}

优化前二维数组：

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b;
double f[5005][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=1; i<=m; i++){
        for(j=0; j<=n; j++){
            if(j < n) f[i][j] += f[i-1][j+1] * (j+1) / n;
            if(j) f[i][j] += f[i-1][j-1] * (n-j+1) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m][i];
    printf("%.6lf\n", ans);
    return 0;
}

从前往后推：

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b;
double f[5005][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=0; i<m; i++){
        for(j=0; j<=n; j++){
            if(j) f[i+1][j-1] += f[i][j] * j / n;
            f[i+1][j+1] += f[i][j] * (n-j) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m][i];
    printf("%.8lf\n", ans);
    return 0;
}