牛客多校第十场

思路

一个随机排列的数列，问前缀和大于$a$的时候小于$b$的概率

思路

大意就是枚举最后一次抽的牌的点数，找在剩下的$n-1$个牌中，前$i$个牌的前缀和范围在$[a-x,min(a,b-x)]$的概率

概率是$\frac{i!(n-i-1)!}{n!}$，这个概率可以预处理出来。

然后就是用可逆背包和滚动数组来求dp

AC代码

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

#define ll long long
const int maxn = 510;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

double dp[2][maxn][maxn], p[maxn];
int x[maxn];

int main() { 
    int n, a, b;
    scanf("%d %d %d", &n, &a, &b);
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &x[i]);
        memcpy(dp[i&1], dp[(i&1)^1], sizeof(dp[0]));
        for (int j = 1; j <= n; j ++) 
            for (int k = x[i]; k <= b; k ++) 
                dp[i&1][j][k] += dp[(i&1)^1][j-1][k-x[i]];
    }
    p[1] = 1./n;
    for (int i = 2; i <= n; i ++)
        p[i] = p[i-1] * (i-1) / (n-i+1);
    double ans = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) 
            for (int k = x[i]; k <= b; k ++)
                dp[n&1][j][k] -= dp[n&1][j-1][k-x[i]];
        for (int j = 0; j < n; j ++)
            for (int k = max(0, a-x[i]+1); k <= a && k + x[i] <= b; k ++) 
                ans += dp[n&1][j][k] * p[j+1];
        for (int j = n; j >= 1; j --) 
            for (int k = b; k >= x[i]; k --) 
                dp[n&1][j][k] += dp[n&1][j-1][k-x[i]];
    }
    printf("%.15f\n", ans);
    return 0;
}

H: Wood Processing

http://www.orzff.cn/f1b7e3b7/