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)$，分两种情况：
得出递推关系式$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,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}^{i*b\leqslant a*n}p(n,i)$
设数学期望为$E$天，第一天晚上有两种情况发生：
根据全期望公式有$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$，分别求直接再抠一枪和随机转一下的条件概率
两者同时乘$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*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<int> cnt(9,4)来存储状态，用map< vector<int> 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$，分两种情况：
由全期望公式得$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; }
原文：https://www.cnblogs.com/zzzzzzy/p/11229596.html
