组合数学&概率&数学期望

A - 容斥原理（CodeForces - 451E）

二进制状态压缩暴力枚举哪几个花选的个数超过了总个数，卢卡斯定理求组合数，容斥原理求答案

可以先把每个花的数量当成无限个，这样就是一个多重集的组合数$ans=C_{n+m-1}^{n-1}$

所以要减去有一种花超过花的数量的情况，加上有两种花超过花的数量的情况，减去有三种花超过花的数量的情况…

最后$ans=C_{n+m-1}^{n-1}-\sum_{i=1}^{n}C_{n+m-a_{i}-2}^{n-1}+\sum_{i=1}^{n}C_{n+m-a_{i}-a_{j}-3}^{n-1}-…+(-1)^{n}C_{n+m-\sum a_{i} -(n+1)}^{n-1}$

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 25;
const int MOD = 1000000007;

ll n, s, f[N];

ll qPow(ll a, ll k, ll p)
{
    ll ans = 1;
    while (k) {
        if (k & 1) ans = (ans * a) % p;
        a = (a * a) % p, k /= 2;
    }
    return ans;
}

ll C(ll a, ll b, ll p)
{
    if (a < b) return 0;
    if (b > a - b) b = a - b;
    ll up = 1, down = 1;
    for (ll i = 0; i < b; i++) {
        up = up * (a - i) % p;
        down = down * (i + 1) % p;
    }
    return up * qPow(down, p - 2, p) % p;
}

ll Lucas(ll a, ll b, ll p) {
    if (b == 0) return 1;
    return C(a%p, b%p, p) * Lucas(a / p, b / p, p) % p;
}

ll solve()
{
    ll res = 0;
    for (int i = 0; i < (1 << n); i++) {
        ll t = s, sign = 1;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) t -= (f[j] + 1), sign *= -1;
        }
        if (t < 0) continue;
        res = (res + sign * Lucas(t + n - 1, n - 1, MOD)) % MOD;
    }
    return (res + MOD) % MOD;
}

int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> f[i];
    cout << solve() << endl;
    return 0;
}

B - 危险的组合（Critical Mass，UVa580）

设答案为$f(n)$，分两种情况：

• 当加入第$n$个元素时组成三个放在一起的U，那么第$n - 1，n - 2$都为U，第$n - 3$为L，保证前$n-4$个元素不会出现三个U放在一起，所以此时有$2^{n-4} - f(n - 4)$种可能
• 当前$n - 1$个元素已经形成了三个放在一起的U，那么第$n$个是U还是L都能形成三个放在一起的U，所以此时有$2 * f(n - 1)$中可能

得出递推关系式$f(n)=2 * f(n - 1) + 2^{n-4} - f(n - 4)$

#include <iostream>

using namespace std;

const int N = 50;

long long cnt[N];

// 快速幂
long long power(long long a, long long n)
{
    long long ans = 1;
    while (n > 0) {
        if (1 == n % 2) ans *= a;
        a *= a; n /= 2;
    }
    return ans;
}

int main()
{
    long long n;
    while (cin >> n && 0 != n) {
        cnt[3] = 1;
        for (int i = 4; i <= n; i++) {
            // 递推公式
            cnt[i] = 2 * cnt[i - 1] + power(2, i - 4) - cnt[i - 4];
        }
        cout << cnt[n] << endl;
    }
    return 0;
}

C - 杆子的排序（Pole Arrangement，UVa1638）

设有$n$个杆子，从左边看能看到$l$根，从右边看能$r$跟时的答案是$f(n,l,r)$，插入高度为n的杆子不好讨论，所以考虑插入高度为1的杆子时的有三种情况：

• 插到最左边，则从左边能看见，从右边看不见，这时有$f(n-1,l-1,r)$种可能
• 插到最右边，则从右边能看见，从左边看不见，这时有$f(n-1,l,r-1)$种可能
• 插到中间（有$n-2$个插入的位置），不管从右边还是左边都看不见，这时有$f(n-1,l,r)*(n-2)$

得出递推关系式$f(n,l,r)=f(n-1,l-1,r)+f(n-1,l,r-1)+f(n-1,l,r)*(n-2)$

#include <iostream>

using namespace std;

const int N = 30;

long long cnt[N][N][N];
long long n, l, r, t;

void init()
{
    cnt[1][1][1] = 1;
    for (long long i = 2; i <= 20; i++) {
        for (long long l = 1; l <= i; l++) {
            for (long long r = 1; r <= i; r++) {
                cnt[i][l][r] = cnt[i - 1][l - 1][r] + cnt[i - 1][l][r - 1] + (i - 2) * cnt[i - 1][l][r];
            }
        }
    }
}

int main()
{
    init(); cin >> t;
    while (t--) {
        cin >> n >> l >> r;
        cout << cnt[n][l][r] << endl;
    }
    return 0;
}

D - 比赛名次（Race，UVa12034）

设答案为$f(n)$，假设第一名有$i$个人，则有$C(n,i)$种可能，接下来的有$f(n-i)$种可能性，所以答案$f(n)=\sum_{i=1}^{i=n} C(n,i)*f(n-i)$，打个表即可

#include <iostream>

using namespace std;

const int N = 1010;
const int P = 10056;

long long C[N][N];
long long F[N];
long long t, n, icas;

void init()
{
    for (int i = 0; i < N; i++) C[i][1] = i, C[i][0] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
        }
    }
    F[0] = F[1] = 1;
    for (int n = 2; n < N; n++) {
        for (int i = n; i >= 1; i--) {
            F[n] = (F[n] + (F[n - i] * C[n][i]) % P) % P;
        }
    }
}

int main()
{
    init(); cin >> t;
    while (t--) {
        cin >> n;
        cout << "Case " << ++icas << ": " << F[n] << endl;
    }
    return 0;
}

E - 麻球繁衍（Tribbles，UVa11021）

由于每只的麻球的后代独立存活，所以只用求出一个麻球$m$天后全部死亡的概率$f(m)$，最后的答案就是$f(m)^{k}$

第一天出生的麻球会在$m-1$后全部死亡，所以$f(m)=P_{0} + P_{1}*f(m-1)+P_{2}*f(m-1)^{2} + …+P_{n-1}*f(m-1)^{n-1}$

第二天出生的麻球会在$m-2$后全部死亡，所以$f(m-1)=P_{0} + P_{1}*f(m-2)+P_{2}*f(m-2)^{2} + …+P_{n-1}*f(m-2)^{n-1}$

到第$i$天全部死亡的概率$f(i)=P_{0} + P_{1}*f(i-1)+P_{2}*f(i-1)^{2} + …+P_{n-1}*f(i-1)^{n-1}$

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

double p[N], f[N];
int t, n, k, m, icas;

int main()
{
    cin >> t;
    while (t--) {
        cin >> n >> k >> m;
        memset(f, 0, sizeof(f));
        for (int i = 0; i < n; i++) cin >> p[i];
        for (int i = 1; i <= m; i++) {
            double tp = 1;
            for (int j = 0; j < n; j++) {
                f[i] += (p[j] * tp), tp *= f[i - 1];
            }
        }
        double res = 1;
        for (int i = 0; i < k; i++) res *= f[m];
        cout << "Case #" << ++icas << ": " << fixed << setprecision(7) << res << endl;
    }
    return 0;
}

F - 玩纸牌（Expect the Expected，UVa11427）

设$p(i,j)$表示玩$i$局赢$j$局的概率，所以当$j>0$时，$p(i,j)=p(i-1,j-1)\frac{a}{b}+p(i-1,j)(1-\frac{a}{b})$，当$j=0$时，第$i$局输，所以$p(i,j)=p(i-1,j)*(1-\frac{a}{b})$

设每天晚上垂头丧气去睡觉的概率为$q$，所以$q=\sum_{i=0}^{ib\leqslant an}p(n,i)$

设数学期望为$E$天，第一天晚上有两种情况发生：

• 第一天晚上垂头丧气去睡觉，概率为$q$，所以能玩纸牌天数的数学期望为1
• 第一天晚上高高兴兴去睡觉，概率为$1 - q$，因为第一天和第二天独立，所以能玩纸牌天数的数学期望为$E + 1$

根据全期望公式有$E = q * 1 + (1 - q) * (E + 1)$，解得$E = 1 / q$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

char ch;
int t, n, a, b, icas;
double p[N][N];

double cal()
{
    memset(p, 0, sizeof(p));
    p[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i && j * b <= a * i; j++) {
            if (j > 0) p[i][j] = p[i - 1][j - 1] * a / b + p[i - 1][j] * (1 - 1.0 * a / b);
            else p[i][j] = p[i - 1][j] * (1 - 1.0 * a / b);
        }
    }
    double q = 0;
    for (int i = 0; i <= n && i * b <= a * n; i++) q += p[n][i];
    return int(1.0 / q);
}

int main()
{
    cin >> t;
    while (t--) {
        cin >> a >> ch >> b >> n;
        cout << "Case #" << ++icas << ": " << cal() << endl;
    }
    return 0;
}

G - 得到1（Race to 1，UVa11762）

设$f(x)$为当前数为$x$时接下来需要操作的次数，不超过$x$的素数个数为$p(x)$，不超过$x$而且能被$x$整除的素数个数为$g(x)$

每一次选取都要操作一次，所以由全概率公式有$f(x)=1+[1-\frac{g(x)}{p(x)}]*f(x)+\sum _{0=x\%y}\frac{f(\frac{x}{y})}{p}$

化简后得$f(x)=\frac{p(x)+\sum _{0=x\%y}\frac{f(\frac{x}{y})}{p}}{g(x)}$

#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;

const int N = 1000010;

int isprime[N];
int prime[N];
int vis[N];
double f[N];
int tot, t, n, icas;

void get_prime(int n)
{
    memset(isprime, 0, sizeof(isprime));
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) prime[++tot] = i;
        for (int j = 1; j <= tot; j++) {
            if (i * prime[j] > n) break;
            isprime[i * prime[j]] = 1;
            if (0 == i % prime[j]) break;
        }
    }
}

double dp(int x)
{
    if (1 == x) return 0;
    if (vis[x]) return f[x];
    vis[x] = 1; int p = 0, g = 0; double ans = 0;
    for (int i = 1; i <= tot && prime[i] <= x; i++) {
        p += 1;
        if (0 == x % prime[i]) { g += 1; ans += dp(x / prime[i]); }
    }
    ans = (ans + p) / g;
    return f[x] = ans;
}

int main()
{
    get_prime(N); cin >> t; f[1] = 0;
    while (t--) {
        cin >> n;
        cout << "Case " << ++icas << ": ";
        cout << fixed << setprecision(10) << dp(n) << endl;
    }
    return 0;
}

H - 决斗（Headshot，UVa1636）

设字符串的长度为$n$，子串中00的个数为$a$，0的个数为$b$，分别求直接再抠一枪和随机转一下的条件概率

• 直接再抠一枪，因为第一个是0，所以在第一个是0的条件下再抠一枪还是0的概率是$\frac{a}{b}$
• 随机转一下还是0的概率即是字串中0的个数，即$\frac{b}{n}$

两者同时乘$b*n$后比较两者大小即可

#include <iostream>
#include <string>

using namespace std;

string s;

int main()
{
    while (cin >> s) {
        int a = 0, b = 0, n = (int)s.size();
        for (int i = 0; i < n; i++) {
            if ('0' == s[i]) a += 1;
            if ('0' == s[i] && '0' == s[(i + 1) % n]) b += 1;
        }
        if (b * n > a * a) cout << "SHOOT" << endl;
        else if (b * n < a * a) cout << "ROTATE" << endl;
        else cout << "EQUAL" << endl;
    }
    return 0;
}

I - 奶牛和轿车（Cows and Cars，UVa10491）

和三门问题一样

• 第一次选到牛的概率为$\frac{a}{a+b}$，打开$c$扇门后换门选到车的概率为$\frac{b}{a+b-c-1}$
• 第一次选到车的概率为$\frac{b}{a+b}$，打开$c$扇门后换门就不能选第一次选的门了，所以这是车的数量为$b-1$，所以选到车的概率为$\frac{b-1}{a+b-c-1}$

所以由全概率公式有赢得车的概率为$\frac{a*b+b*(b-1)}{(a+b)*(a+b-c-1)}$

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    double a, b, c;
    while (cin >> a >> b >> c) {
        double res = (b * (a + b - 1)) / ((a + b) * (a + b - c - 1));
        cout << fixed << setprecision(5) << res << endl;
    }
    return 0;
}

J - 条件概率（Probability|Given，UVa11181）

条件概率的公式为$p(E_{i}|E)=\frac{p(E_{i} E)}{p(E)}$

所以要通过深搜算出$n$个人中$r$买物品的概率$p(E)$，算出第$i$个人买物品的同时有$r$个人买物品的概率$p(E_{i} E)$

#include <iostream>
#include <iomanip>
#include <cstring>

using namespace std;

const int N = 25;

int n, r, icas;
double p[N], sum[N], tot;

void dfs_tot(int cur, int num, double q)
{
    if (cur == n) {
        if (num == r) tot += q;
        return;
    }
    else {
        dfs_tot(cur + 1, num + 1, q * p[cur]);
        dfs_tot(cur + 1, num, q * (1 - p[cur]));
    }
}

void dfs_sum(int cur, int num, double q, int idx)
{
    if (cur == n) {
        if (num == r - 1) sum[idx] += q;
        return;
    }
    else {
        if (cur != idx) {
            dfs_sum(cur + 1, num + 1, q * p[cur], idx);
            dfs_sum(cur + 1, num, q * (1 - p[cur]), idx);
        }
        else dfs_sum(cur + 1, num, q, idx);
    }
}

int main()
{
    while (cin >> n >> r) {
        memset(sum, 0, sizeof(sum)), tot = 0;
        if (0 == n && 0 == r) break;
        for (int i = 0; i < n; i++) cin >> p[i];
        dfs_tot(0, 0, 1);
        for (int i = 0; i < n; i++) {
            dfs_sum(0, 0, 1, i); sum[i] *= p[i];
        }
        cout << "Case " << ++icas << ":" << endl;
        for (int i = 0; i < n; i++) {
            cout << fixed << setprecision(6) << sum[i] / tot << endl;
        }
    }
    return 0;
}

K - 纸牌游戏（Double Patience，UVa1637）

用九元组vector cnt(9,4)来存储状态，用map< vector cnt, double > mp来映射一个状态的成功的概率

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const int N = 9;
const int M = 4;

map< vector<int>, double > mp;
char ch[N][M][2];

// 读取
bool read_card()
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (scanf("%s", ch[i][j]) != 1) return false;
        }
    }
    return true;
}

// cnt表示牌堆状态，c表示现在卡牌的数量
double dp(vector<int> &cnt, int c)
{
    if (0 == c) return 1;
    if (0 != mp.count(cnt)) return mp[cnt];
    int tot = 0; double sum = 0;
    for (int i = 0; i < N; i++) { // 选中的第一个牌堆
        for (int j = i + 1; j < N; j++) { // 选中的第二个牌堆
            if (cnt[i] && cnt[j] && ch[i][cnt[i] - 1][0] == ch[j][cnt[j] - 1][0]) {
                // 两个牌堆都有牌而且顶部的卡牌满足要求
                cnt[i] -= 1, cnt[j] -= 1;
                tot += 1, sum += dp(cnt, c - 2);
                cnt[i] += 1, cnt[j] += 1;
            }
        }
    }
    if (!tot) return mp[cnt] = 0;
    else return mp[cnt] = sum / tot;
}

int main()
{
    while (read_card()) {
        vector<int> cnt(9, 4); // 初始化状态，9个牌堆，一个牌堆4张牌
        mp.clear();
        printf("%.6lf\n", dp(cnt, 36));
    }
    return 0;
}

L - 过河（Crossing Rivers，UVa12230）

由于船在每个位置概率是相等的，所以过每条河的时间为$\frac{L}{v}$到$\frac{3* L}{v}$均匀分布，因此过河时间为$\frac{2* L}{v}$，再加上$D-sum(L)$

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 15;

double p[N], l[N], v[N];
double n, d, sum_l, res;
int icas;

int main()
{
    while (cin >> n >> d) {
        if (0 == n && 0 == d) break;
        sum_l = 0, res = 0;
        for (int i = 0; i < n; i++) {
            cin >> p[i] >> l[i] >> v[i];
            sum_l += l[i], res += 2 * l[i] / v[i];
        }
        res += (d - sum_l);
        cout << "Case " << ++icas << ": ";
        cout << fixed << setprecision(3) << res << endl << endl;
    }
    return 0;
}

M - 糖果（Candy，UVa1639）

假设最后一次打开第一个盒子，此时第二个盒子有$i$颗糖，则在这之前一共打开过$2*n-i$次盒子，其中有$n$次打开第一个盒子，最后一次要打开第一个盒子，所以概率为$C_{2*n-i}^{n}*p^{n+1}*(1-p)^{n-i}$

取对数有$v1(i)=In(C_{2*n-i}^{n})+(n+1)*In(p)+(n-i)*In(1-p)$，化简的$In(C_{2*n-i}^{n})=In\frac{(2*n-i)!}{n!*(n-i)!}=\sum _{k=1}^{2*n-i}In(k)-\sum _{k=1}^{n}In(k)$

所以$v1(i)=\sum _{k=1}^{2*n-i}In(k)-\sum _{k=1}^{n}In(k)+(n+1)*In(p)+(n-i)*In(1-p)$

同理$v2(i)=\sum _{k=1}^{2*n-i}In(k)-\sum _{k=1}^{n}In(k)+(n+1)*In(1-p)+(n-i)*In(p)$

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

const int N = 200010;

long double logc[2 * N];
long double p, res;
int n, icas;

void init()
{
    for (int i = 1; i < 2 * N; i++) logc[i] = logc[i - 1] + log(i);
}

int main()
{
    init();
    while (cin >> n >> p) {
        res = 0;
        for (int i = 1; i <= n; i++) {
            long double c = logc[2 * n - i] - logc[n] - logc[n - i];
            long double v1 = c + (n + 1) * log(p) + (n - i) * log(1 - p);
            long double v2 = c + (n + 1) * log(1 - p) + (n - i) * log(p);
            res += (i * (exp(v1) + exp(v2)));
        }
        cout << "Case " << ++icas << ": ";
        cout << fixed << setprecision(6) << res << endl;
    }
    return 0;
}

N - 优惠券（Coupons，UVa10288）

当已经拿到$k$张后，拿第$k+1$张时，拿到的概率为$Q=\frac{n-k}{n}$

设拿到第$k+1$的期望为$E$，分两种情况：

第一次就拿到第$k+1$张，概率为$Q$，期望是1
第一次没有拿到，因为每次拿都是独立的，所以概率为$1-Q$，期望是$E+1$
由全期望公式得$Q+(1-Q)*(E+1)=E$，解得$E=\frac{1}{Q}=\frac{n}{n-k}$

所以答案为$\sum _{k=0}^{n-1}\frac{n}{n-k}$

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll n, n_up, n_down, pre;
ll num_pre, num_n_up, num_n_down;

ll gcd(ll a, ll b)
{
    return 0 == b ? a : gcd(b, a % b);
}

void cal(ll up, ll down)
{
    ll tp_up = n_up * down + n_down * up;
    ll tp_down = n_down * down;
    pre += (tp_up / tp_down), tp_up %= tp_down;
    ll gcd_num = gcd(tp_up, tp_down);
    if (0 != gcd_num) n_up = tp_up / gcd_num, n_down = tp_down / gcd_num;
    else n_up = tp_up, n_down = tp_down;
}

int main()
{
    while (cin >> n) {
        n_up = n_down = n, pre = 0;
        num_pre = num_n_up = num_n_down = 0;
        for (ll i = n - 1; i >= 1; i--) cal(n, i);
        ll tp_n_up = n_up, tp_n_down = n_down, tp_pre = pre;
        if (0 == n_up) cout << pre << endl;
        else if (0 == pre) cout << 1 << endl;
        else {
            while (tp_n_up) num_n_up += 1, tp_n_up /= 10;
            while (tp_n_down) num_n_down += 1, tp_n_down /= 10;
            while (tp_pre) num_pre += 1, tp_pre /= 10;
            ll num_ = max(num_n_up, num_n_down);
            for (int i = 0; i < num_pre + 1; i++) cout << " ";
            cout << n_up << endl;
            cout << pre << " ";
            for (int i = 0; i < num_; i++) {
                if (i == num_ - 1) cout << "-" << endl;
                else cout << "-";
            }
            for (int i = 0; i < num_pre + 1; i++) cout << " ";
            cout << n_down << endl;
        }
    }
    return 0;
}