【题解】[SHOI2002]百事世界杯之旅

$\text{min-max}$ 容斥！

题目链接：[SHOI2002]百事世界杯之旅

题意：

有 $n$ 个物品，每次等概率选择一个（一个物品可重复选择），求得到所有物品的期望次数。

$2\le n\le 33$。

看起来这题有一个很简单的做法，但是本人第一眼就是 $\text{min-max}$ 容斥啊......

众所周知：

$$max(S)=\sum _{T\subseteq S}(-1{)}^{|T|-1}min(T)$$

需要注意的是这个柿子套上期望也是成立的，即：

$$E(max(S))=\sum _{T\subseteq S}(-1{)}^{|T|-1}E(min(T))$$

这里不妨直接设 $min(S)$ 为得到 $S$ 中任意元素的最少次数，$max(S)$ 为得到 $S$ 中所有元素的次数。

那么显然 $E(min(S))={\displaystyle \frac{n}{|S|}}$，因为一次操作选中一个 $S$ 中元素的概率的概率是 ${\displaystyle \frac{|S|}{n}}$，期望就是其倒数。

那么可以把答案写成：

$$\text{Ans}=\sum _S(-1{)}^{|S|-1}{\displaystyle \frac{n}{|S|}}$$

发现柿子只和 $S$ 的大小有关了，转变为枚举 $|S|$。显然的，大小为 $x$ 的集合个数是 $(\genfrac{}{}{0ex}{}{n}{x})$。

枚举 $|S|$，答案可以写成：

$$\text{Ans}=\sum _{i=1}^n(-1{)}^{i-1}\times {\displaystyle \frac{n}{i}}\times (\genfrac{}{}{0ex}{}{n}{i})$$

组合数只要求一行，直接 $\mathcal{O}(n)$ 递推，然后就可以按上述柿子模拟。

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

//#define FILE
#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define vec vector

const int MAXN = 110;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int Gcd(int x, int y) {
    if(!y) return x;
    return Gcd(y, x % y);
}

struct Frac {
    int a, b;
    Frac(int _a = 0, int _b = 0) : a(_a), b(_b) {}
    Frac operator + (const Frac &x) const {
        return Frac(a * x.b + b * x.a, x.b * b);
    }
    void clear() {
        static int gcd; gcd = Gcd(a, b);
        a /= gcd, b /= gcd;
    }
} Ans(0, 1);

int n, m, C;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
    return 1;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

int count(int x) {
    int res = 0;
    for(; x; x /= 10, res++);
    return res;
}

signed main () {
    read(n); C = 1;
    for(int i = 1, opt = 1; i <= n; ++i) {
        C = C * (n - i + 1) / i;
        Frac now = Frac(opt * n * C, i);
        now.clear();
        Ans = Ans + now; Ans.clear();
        opt *= -1;
    }
    Ans.clear();
    int x = Ans.a / Ans.b, y = Ans.a % Ans.b, z = Ans.b;
    if(z == 1) return printf("%lld\n", x), 0;
    if(!x) {
        int tmp = max(count(y), count(z));
        printf("%lld\n", y);
        for(int i = 1; i <= tmp; ++i) putchar('-');
        printf("\n%lld\n", z);
    } else {
        int tmp1 = max(count(y), count(z)), tmp2 = count(x);
        for(int i = 1; i <= tmp2; ++i) putchar(' ');
        printf("%lld\n%lld", y, x);
        for(int i = 1; i <= tmp1; ++i) putchar('-');
        printf("\n");
        for(int i = 1; i <= tmp2; ++i) putchar(' ');
        printf("%lld\n", z);
    }
    return 0;
}