XSY contest1586 proB

佚名 6年前 (2019-04-11) 随笔 1311人围观抢沙发百度已收录

题目

现在一圈n个花坛，每次随机往一个花盆里种花，一个花盆可以种多颗花，假如一个花盆两边的花盆都有花，那么他也将被种上花
问期望种满所有花盆要种几次
首先定义f(i)为放置了i个物品后完全覆盖的概率，可以发现
\[f[i] = \frac{C_i^{n-i}}{C_{n - 1}^{i - 1}}\]
那么答案就是\[\sum_{i=0}^{n - 1}(1 - f[i]) \frac{n}{n - i}\]
On了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define M 10000100
#define mmp make_pair
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}

int fac[M], inv[M], n;
const int mod = 1000000007;
void add(int &x, int y) {
    x += y;
    x -= x >= mod ? mod : 0;
}
int mul(int a, int b) {
    return 1ll * a * b % mod;
}
int poww(int a, int b) {
    int ans = 1, tmp = a;
    for(; b; b >>= 1, tmp = mul(tmp, tmp)) if(b & 1) ans = mul(ans, tmp);
    return ans;
}

int C(int n, int m)
{
    if(m > n || n < 0 || m < 0) return 0;
    return mul(fac[n], mul(inv[m], inv[n - m]));
}
 
int Inv(int x) {
    return mul(inv[x], fac[x - 1]);
}

int invC(int n, int m)
{
    return mul(inv[n], mul(fac[m], fac[n - m]));
}

int f(int i)
{
    return (1 - mul(C(i, n - i), invC(n - 1, i - 1)) + mod) % mod;
}

int main() {
    n = read();
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
    inv[n] = poww(fac[n], mod - 2);
    for(int i = n - 1; i >= 1; i--) inv[i] = mul(inv[i + 1], i + 1);
    int ans = 0;
    for(int i = 0; i < n; i++) add(ans, mul(mul(n, Inv(n - i)), f(i)));
    cout << ans << "\n";
    return 0;
}