演算法講堂二：組合數學 & 概率期望DP
- 2020 年 6 月 6 日
- 筆記
- 刷題筆記----------
組合數學
1. 排列組合
1. 加法原理
完成一列事的方法有 n 類，其中第 i 類方法包括\(a_i\)種不同的方法，且這些方法互不重合，則完成這件事共有 \(a_1 + a_2 + \cdots + a_n\) 種不同的方法
2. 乘法原理
若完成一件事需要 n 個步驟，其中第 i 個步驟有 \(a_i\) 種不同的完成方法，且這些步驟互不干擾，則完成這件事共有 \(a+1 * a_2 * \cdots * a_n\) 種不同的方法
兩原理的區別：
一個與分類有關，一個與分步有關；加法原理是「分類完成」，乘法原理是「分步完成」
3. 排列數
在 \(n\) 個不同元素種，任取 \(與均為自然數，下同m(m\leq n,m與n均為自然數，下同)\) 個元素按照一定的順序排成一列，叫做從\(n\)個不同元素中取出\(m\) 個元素的一個排列；產生排列的個數叫做從 \(n\) 個不同元素中取出 \(m\)個元素的排列數，用符號 \(A_n^m\) 來表示
\]
排列分為全排列和部分排列，全排列的m = n
4. 組合數
從 n 個不同元素中，任取\(m (m\leq n)\)個元素組成一個集合，叫做從n 個不同元素中取出m 個元素的一個組合；從n個不同元素中取出\(（m （m\leq n)\) 個元素的所有組合的個數，叫做從n 個不同元素中取出m 個元素的組合數。用符號\(或者是C_n^m (或者是 (^m_n) )\)表示
\]
組合數性質
- \(C_n^m = C_n^{n-m}\)
- \(C_n^m = C_{n-1} ^ m + C_{n-1} ^{m-1}\) (可用楊輝三角推到)
- \(C_n^0 + C_n^1 + C_n^2 + C_n^3 + \cdots + C_n^n = 2^n\)
- $\sum_{i=0}^m C_n^i C_m^{m-i} = C_{m+n}^m(n \geq m) $ 分開取和一起取是一樣的（也可以理解成先取和後取）
5. 多重集的排列數
設集合 \(S = {n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k}\) ,是由\(n_1\) 個\(a_1\)，\(n_2\)個\(a_2\)\(\cdots\) \(n_k\) 個 \(a_k\) 組成的多重集。S的全排列個數為：
\]
6. 多重集的組合數
n種不一樣的球，每種球的個數是無限的，從中選k個出來組成一個多重集（不考慮元素的順序），產生的不同多重集的數量為：
\(C_{n+k-1} ^ {k-1}\)
如何證明？
設第 i 個元素選\(x_i\) 個，問題轉化為方程\(x_1+x_2+\cdots+x_n = k\)的非負整數解的個數。令\(y_i = x_i + 1\) ,則答案為\(y_1+y_2+\cdots y_n = k + n\) 的正整數解的個數。也就是說有\(k+n\) 個 」1「 排成一排，問題等價於把這些「1」 分成 k 個部分，有多少種方法？
7. 不相鄰的排列
\(1\sim n\) 這 n 個自然數中選k 個，這k 個數中任何兩個數不相鄰數的組合有 \(C_{n-k+1}^k\)種
設取出來的k個數為：
\(1 < b_1 < b_2 < b_3 < \cdots < b_k \le n\)
要保證兩數字沒有相鄰，那麼兩數相差至少間隔一
$1 \le b_1 < b_2-1 < b_3-2 < b_4-3 < \cdots < b_k-k+1 \le n-k+1 $
在這裡，轉換為了C系列，設\(c[i] = b[i] – i + 1\) ，所以
$1 \le c_1 < c_2 < c_3 < c_4 < \cdots < c_k \le n-k+1 $
所以問題就變成：在n-k+1個元素種選中k 個組合數\(C_{n-k+1}^k\)
8. 錯位排列
胸口貼著編號為\(1,2,\cdots,n\) 的 n 個球員分別住在編號為\(1,2,\cdots ,n\) 的n個房間裡面。現規定每個人住一個房間，自己的編號不能和房間的編號一樣
設答案為 \(d[n]\)
只考慮第 n 個人，
假如n指定要和第 i 個人互換房間，那麼其他 n – 2 個人怎麼分不關他們的事情，這樣的 i 有 n – 1 個，故這種情況對答案的貢獻是\((n-1)\) 個 \(d[n-2]\)。
假如n只是要第 i 個人到他的房間，但他自己不去第 i 個房間，也就是說不是互換，那麼該怎麼思考呢？既然n不到第 i 個房間，那可以讓n把自己胸口貼的標號換成 i ，假裝自己是 i，然後錯排\(1\sim n\) 。這樣他自己就一定不會呆在第 i 個房間了。所以有 n-1 個 d[n-1].
故答案為 \(d[n] = (n-1)(d[n-1] + d[n-2]) (n\ge 3)\)
同時也有 \(d[n] = n \times d[n-1]+ (-1)^n\)
9. 圓排列
n 個人全部來圍成一圈為\(Q_n^n\) ，其中已經排好的一圈，從不同位置斷開，又變成不同的隊列。所以：\(Q_n^n \times n = A_n^n \rarr Q_n = (n-1)!\)
由此可知部分圓排列為 \(Q_n^r = {A_n^r \over r} = {n! \over r \times (n-r)!}\)
組合數求法
- 遞推公式\(O(n^2)\)
- 定義（預處理階乘）
- 數字比較大階乘會爆的話就會取模。然後除法用逆元來算，盧卡斯可以更好的做這件事情
盧卡斯定理
$C_n^k = C_{n\over p}^{k\over p} * (mod $ \(p )\)
洛谷P3807
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int T;
ll n,m,p;
ll j[N];
ll pow(ll a,ll b ,ll p){
ll res = 1;
for(;b;b>>=1){
if(b & 1) res = (res * a)%p;
a = a * a % p;
}
return res;
}
ll C(ll n,ll m){
if(m > n)return 0;
return ((j[n] * pow(j[m],p-2,p))%p * pow(j[n-m],p-2,p)%p);
}
ll Lucas(ll n,ll m){
if(!m)return 1;
return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int main(){
j[0] = 1;
cin>>T;
while(T--){
cin >> n >> m >> p;
for(int i=1;i<=p;i++)
j[i] = j[i-1] * i % p;
cout<<Lucas(n+m,n)<<endl;
}
return 0;
}
2. 卡特蘭數
引子：給一個凸多邊形，用n-3條不相交的對角線把它分成n-2個三角形，求不同的方法數目
- 邊\(V_1V_n\)在最終的剖分種一定會恰好屬於某個三角形\(V_1V_nV_k\)
- 兩條邊將多邊形劃分為了一個k邊形和一個\(n-k+1\)邊形
故\(f(n) = f(2)f(n-1) + f(3)f(n-2)+\cdots + f(n-1)f(2)\)
另一種思路：
考慮\(V_1\) 的連線
\(n(f(3)f(n-1) + f(4)f(n-2)+\cdots + f(n-1)f(3)\) 個部分
因為每個方案被計算了2n-6次，
\(f(n) = (f(3)f(n-1) + f(4)f(n-2)+\cdots + f(n-1)f(3))\times n/(2n-6)\)
上面兩式合併可得：\(f(n+1) = {4n-6\over n}f(n)\)
上述這一種是紫書上面的推到方法，\(f(1) = f(2) = 1\)
另一種例子
n 個 0， n 個1，排列m長度序列，滿足任意前綴種0的個數不少於1的個數的序列的數量為\(Cat_n = {C_{2n}^n\over n+1}\)
若S不滿足：任意前綴0的個數不小於1的個數
則至少存在一個最小的位置 \(2*p+1\in [1,2n]\) 使得\(s[1\sim 2p+1]\) 中有p個0，p+1個1
而把\(s[2p+2\sim 2n]\)中的所有數字取反後，包含n-p-1個0，n-p個1於是得到了n-1個0，n+1個1的序列
同理，令n-1個0，與n+1個1隨意排成的序列，也必有一個最小的位置\(2p’+1\)，
使得\(s'[1\sim2p’+1]\) 中有p’個0，p』+1個1
把s’剩下的一半取反，n個0，n個1排成的，存在一個前綴0比1多的序列
因此，以下兩種序列構成一種雙射
- 由n個0，n個1構成的，存在一個前綴0比1多的序列
- 由n-1個0與n+1個1排成的序列
根據組合數定義，後者有\(C_{2n}^{n-1}\)個
故\(C_{2n}^n-C_{2n}^{n-1} = {C_{2n}^n\over n+1}\)
\(f(0) = f(1) = 1\)
卡特蘭數的其他例子
- 有 2n個人排成一行進入劇場。入場費 5 元。其中只有n 個人有一張 5 元鈔票，另外 n人只有 10 元鈔票，劇院無其它鈔票，問有多少中方法使得只要有 10 元的人買票，售票處就有 5 元的鈔票找零？
- 一個棧（無窮大）的進棧序列為 n有多少個不同的出棧序列？
- n個結點可夠造多少個不同的二叉樹？
- 一位大城市的律師在她住所以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果他從不穿越（但可以碰到）從家到辦公室的對角線，那麼有多少條可能的道路？
3. 斯特林數
第一類斯特林數
把n個不同的球分成r個非空循環排列的方法數
遞推形式 : \(s(n,r) = (n-1)s(n-1,r) + s(n-1,r-1),n>r \ge 1\)
考慮最後一個球，他可以單獨構成一個非空循環排列，也可以插入到前面一個球的一側。
若單獨，則\(s(n-1,r-1)\) ，若放在某個球的一側，則\((n-1)s(n-1,r)\)
第二類斯特林數
把n個不同的球放到r個盒子里，假設沒有空盒，則放球方案數記作S(n,r)，稱為第二類Stirling數
\(S(n,r) = rS(n-1,r) + S(n-1,r-1),n>r\ge 1\)
//acm.hdu.edu.cn/showproblem.php?pid=3625
4. 康托展開
求一個\(1\sim n\)的任意排列的排名
根據字典序排序，比如4的排列：[2,3,1,4] < [2,3,4,1]，因為第3位出現不同，則[2,3,1,4]的排名在[ 2,3,4,1]前面。
給定一個排列，求它的排名。例子:[2,5,3,4,1]
- 小於2 的數字為1，故有4!個排列在它前面
- 小於5的數字有1，2，3，4，但是2在前面用過了，所以有三個，故為3*3!
- 小於3的數字有1，2，2在前面用了，所以有一個，故為2！
- …
- 答案為4! + 3*3! + 2! + 1 + 1 = 46，因為是計算排名，所以要多加一個1
每次要用到當前有多少個小於它的數還沒有出現，這裡用樹狀數組統計比它小的數出現過的次數就行了。
那如何通過給定一個排名來求排列呢？（即逆康托展開）
如果我們知道一個排列的排名，就可以逆推出這個排列。因為4！是嚴格大於\(3\times 3! + 2\times 2! + 1\times 1!\) 的，所以可以認為對於長度為5的排列，排名x除以4！向下取整就是有多少個數小於這個排列的第一位。
46-1 = 45
- \(\lfloor{45\over 4!}\rfloor = 1\) ，有一個數小於它，所以第一位是2
- 45 – 4! = 21,\(\lfloor{21\over 3!}\rfloor = 3\) ，有三個數小於它，去掉已經存在的2，這一位是5。
- \(21-3\times 3! = 3\) \(\lfloor {3\over 2!}\rfloor = 1\)，有一個數小於它，那麼這一位就是3
- …
暴力\(O(n^2)\)，用線段樹二分可以優化到\(O(nlogn)\)
5. 容斥原理
\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|\)
設 U 中元素有 n 種不同的屬性，而第 i 種屬性稱為 $P_i \(, 擁有屬性\)P_i$ 的元素構成集合\(S_i\)，那麼 $$ \begin{split} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\ &+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}{m}S_{a_i}\right|+\cdots+(-1){n-1}|S_1\cap\cdots\cap S_n| \end{split} $$ 即： $$ \left|\bigcup_{i=1}{n}S_i\right|=\sum_{m=1}n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| $$ 補集： $$ \left|\bigcap_{i=1}{n}S_i\right|=|U|-\left|\bigcup_{i=1}n\overline{S_i}\right| $$
多重集的組合數（不定方程非負整數解計數）
給出不定方程\(\Sigma_{i=1}^nx_i = m\) 和 n 個限制條件\(x_i \leq b_i\)，其中\(m,b_i\leq N\),求方程的非負整數解的個數
若沒有\(x_i \le b_i\)的限制，那麼答案是\(C_{m+n-1}^{n-1}\) 證明用插板法
容斥模型：
-
全集U ： 不定方程\(\Sigma_{i=1}^nx_i = m\)的非正整數解
-
元素：變數\(x_i\)
-
屬性：\(x_i\) 的屬性即\(x_i\)滿足的條件，即\(x_i\leq b_i\)的條件
-
目標：所有變數滿足對應屬性時集合的大小，即\(|\bigcap_{i=1}^nS_i|\) $$ \left|\bigcap_{i=1}{n}S_i\right|=|U|-\left|\bigcup_{i=1}n\overline{S_i}\right| $$ \(|U|\)可以用組合數計算，後半部分用容斥定理計算
\(\overline{S_i}\) 的含義是表示至少包含\(b_i+1\)個\(a_i\)的多重集。
則\(\overline{S_i}\)的個數是：\(C_{n+m-b_i-2}^{n-1}\)
進一地，\(\overline{S_i}\overline{S_j}\) 為：\(C_{n+m-b_i-b_j-3}^{n-1}\)
由容斥定理 $$ \left|\bigcup_{i=1}^m\overline{S_i}\right| = \sum_{i=1}mC_{n+m-b_i-2}{n-1} – \sum_{1\leq i<j\leq m}C_{n+m-b_i-b_j-3}{n-1}+\cdots +(-1){m+1}C_{n+m-\sum_{i=1}mn_i-(m-1)}{n-1} $$
例題：Devu and Flowers（CF451E）
Devu有N個盒子，第 i 個盒子中有\(A_i\)枝花。同一個盒子內的花顏色相同，不同盒子內的花顏色不同。Devu要從這些盒子中選出M枝花組成一束，求共有多少種方案。若兩束花每種顏色的花的顏色都相同，則認為這兩束花是相同的方案。輸出對\(10^9+7\)取模之後的結果即可。\(1\leq N\leq20,1\le M\le 10^{14},0\leq A_i\leq 10^{12}\)
- 二進位枚舉
- N很小，M很小，計算組合數會爆ll
- Lucas，乘法逆元
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; ll a[22],j[22],m,ans=0; ll inv[22],n; ll power(ll a,ll b){ ll res = 1; for(;b;b>>=1){ if(b & 1)res = (res * a)%mod; a = a*a%mod; } return res; } ll C(ll y,int x){ if(y < 0 || x < 0 || y < x)return 0; y %= mod; if(y == 0 || x == 0)return 1; ll res = 1; for(int i=0;i<x;i++){ res = res * (y-i) % mod; } //res = res * inv[x] % mod; for(int i=1;i<=x;i++) res = res * inv[i]%mod; return res; } int main(){ j[0] = 1; for(int i=1;i<=20;i++){ //j[i] = j[i-1] * i % mod; inv[i] = power(i,mod-2); } scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int x=0;x < (1<<n);x++){ if(x == 0) ans = (ans + C(n+m-1,n-1)) % mod; else{ ll t = n + m; int p = 0; for(int i=0;i<n;i++){ if(x >> i & 1){ p ++ ; t -= a[i+1]; } } t -= p + 1; if(p & 1) ans = (ans - C(t,n-1))%mod; else ans = (ans + C(t,n-1))%mod; } } printf("%lld\n",(ans + mod) % mod); return 0; }
例題：HAOI2008 硬幣購物
//www.luogu.org/problemnew/show/P1450
4種面值的硬幣，第 i 種的面值是\(C_i\)。n次詢問，每次詢問給出每種硬幣的數量\(D_i\)和一個價格S，問付款方式。\(n\leq 10^3 ,S\leq 10^5\)
如果用背包做的話，複雜度是O(4nS)，無法承受。
\(\sum_{i=1}^4C_ix_i = S, x_i\leq D_i\)的非負整數解的個數
採用同樣的容斥方式，\(x_i\)的屬性為\(s_i\leq D_i\)，套用容斥原理的公式 $$ \sum_{i=1}^4C_ix_i = S-\sum_{i=1}^kC_{a_i}(D_{a_i}+1) $$ S可由無限背包來打表求，後面的用容斥定理
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[5],d[5],tot,s;
ll f[100010];
int main(){
scanf("%lld%lld%lld%lld%lld",&c[1],&c[2],&c[3],&c[4],&tot);
f[0] = 1;
for(int j=1;j<=4;j++){
for(int i=1;i<=100000;i++){
if(i >= c[j]){
f[i] += f[i-c[j]];
}
}
}
while(tot--){
scanf("%lld%lld%lld%lld%lld",&d[1],&d[2],&d[3],&d[4],&s);
ll res = 0;
for(int i=1;i<16;i++){
ll t = s,p = 0;
for(int j=0;j<4;j++){
if((i >> j) & 1)
t -= (d[j+1] + 1) * c[j+1],p++;
}
if(t >= 0){
if(p & 1) res += f[t];
else res -= f[t];
}
}
printf("%lld\n",f[s] - res);
}
return 0;
}
Mobius函數
\(\mu\) 為莫比烏斯函數 $$ \mu(n)= \begin{cases} 1&n=1\ 0&n\text{ 含有平方因子}\ (-1)^k&k\text{ 為 }n\text{ 的本質不同質因子個數}\ \end{cases} $$ 通俗的講，當n包含相等的質因子時，\(\mu(N)=0\) 。當N的所有質因子各不相等時，若N有偶數個質因子，\(\mu(N) = 1\)，若N有奇數個質因子，\(\mu(N)=-1\) 。
若只求一項Mobius函數，則分解質因數即可計算，若求 \(1\sim N\)的每一項Mobius函數，可以利用線性篩法來求mobius函數
void getMu(){
mu[1] = 1;
for(int i=2;i<=n;++i){
if(!v[i])p[++tot] = i,mu[i] = -1;
for(int j=1;j<=tot && i * p[j] <= n;++j){
flg[i * p[j]] = 1;
if(i % p[j] == 0){
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = - mu[i];
}
}
}
6.抽屜原理（鴿巢原理）
就比如說，你有 n+1 個蘋果，想要放到 n 個抽屜里，那麼必然會有至少一個抽屜里有兩個（或以上）的蘋果。
這個定理看起來比較顯然，證明方法考慮反證法：假如所有抽屜都至多放了一個蘋果，那麼 n個抽屜至多只能放n個蘋果，矛盾。
概率&數學期望
1. 概率
定義
如果在相同條件下，進行了n次試驗，事件A發生了\(N_A\)次，那麼\(N_A \over n\)被稱為事件A發生的概率
公理
- 非負性：對於一個事件A，有概率\(P(A)\in [0,1]\)
- 規範性：事件空間的概率值為1，\(P(S) = 1\)
- 容斥性：若\(P(A+B) = P(A)+P(B)\)，則 A 和 B 互為獨立事件。
計算
全概率公式
若事件\(A_1,A_2,\cdots ,A_n\)構成一個完備的事件且都有正概率，即\(且\forall i,j,A_i\cap A_j=\varnothing 且\sum_{i=1}^nA_i=1\)，有\(P(B) = \sum_{i=1}^nP(A_i)P(B|A_i))\)
例子：參加比賽拿金概率0.1，拿銀概率0.2，拿銅概率0.3，這三種情況下，你被媽媽表揚的概率是：1.0，0.8，0.6，那麼你被媽媽表揚的總概率就是\(0.1\times 1.0+0.2\times 0.8+0.3\times 0.6 = 0.44\)
貝葉斯公式
\]
2.期望
定義
在一定區間內變數取值為有限個，或數值可以一一列舉出來的變數稱為離散型隨機變數。一個離散型隨機變數的數學期望是在試驗中每次可能的結果乘以其結果概率的總和。
性質
全期望公式 ：\(E(Y) = E[E(Y|X)]\)。可由全概率公式證明。
線性性質 ：對於任意兩個隨機事件\(x,y\)（不要求相互獨立），有\(E(X+Y) = E(X) + E(Y)\)
例題
1. 麻球繁衍(UVA-11021)
有k只麻球，每隻活一天就會死亡，臨死之前可能會生出一些新的麻球。具體來說，生 i 個麻球的概率為\(P_i\)。給定m，求m天后所有麻球均死亡的概率。注意，不足m天時就已全部死亡的情況也算在內。
核心：遞推，找出遞推所依靠的東西
\(f(i)\)為一開始只有一個麻球的時候，在 i 天后所有麻球均死亡的概率。
則有：\(f(i) = P_0 + P_1 *f(i-1) + P_2*[f(i-1)]^2 + \cdots + P_{n-1}*[f(i-1)]^{n-1}\)
因為每個麻球死亡是獨立的。所以答案為\(f(m)^k\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
double f[N],p[N];
int n,m,k;
int main(){
int T;scanf("%d",&T);
int cas = 0;
while(T--){
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;i++)scanf("%lf",&p[i]);
for(int i=1;i<=m;i++){
double t = 1;
f[i] = 0;
for(int j=0;j < n;j++){
f[i] += t * p[j];
t *= f[i-1];
}
//cout << i << ' ' << f[i] << endl;
}
double res = 1;
for(int i=0;i<k;i++){
res *= f[m];
}
printf("Case #%d: %.6f\n",++cas,res);
}
return 0;
}
2. 玩紙牌（UVA-11427）
每天晚上你都玩紙牌遊戲，如果第一次就贏了就高高興興地去睡覺，如果輸了就繼續玩。假設每盤遊戲你獲勝地概率都是p，且各盤遊戲的輸贏都是獨立的。你是一個固執的完美主義者，因此會一直玩到當晚獲勝局面的比例嚴格大於p時才停止，然後高高興興地去睡覺。當然，晚上的時間有限，最多只能玩n盤遊戲，如果獲勝比例一直不超過p的話，你只能垂頭喪氣地去睡覺，以後再也不玩紙牌了。你的遊戲是計算出平均情況下，你會玩多少個晚上的紙牌。
#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int a,b;
double d[N][N];//i局獲勝j局概率
int n;
int main(){
int T;scanf("%d",&T);int cas = 0;
while(T--){
scanf("%d/%d %d",&a,&b,&n);
memset(d,0,sizeof d);
d[0][0] = 1.0;
for(int i=1;i<=n;i++){
for(int j=0;j <= i && j * b <= a * i;j++){
if(j > 0)
d[i][j] = d[i-1][j-1] * a / b + d[i-1][j] * (1.0 - a * 1.0 / b);
else d[i][j] = d[i-1][j] * (1 - a * 1.0 / b);
}
}
double Q = 0;
for(int i=0;i<n;i++)Q += d[n][i];
//cout << Q << endl;
printf("Case #%d: %d\n",++cas,(int)(1.0/Q));
}
return 0;
}
3. 得到1（UVA 11762)
給出一個整數N，每次可以在不超過N的素數中隨機選擇一個P6 ，如果P是N的約數，則把N變成N/P，否則N不變。問平均情況下需要多少次隨機選擇，才能把N變成1？比如N=3時答案為2，N=13時答案為6
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
double d[N],vis[N];
int T,n;
int p[N],v[N],tot;
void primes(){
for(int i=2;i<N;i++){
if(!v[i])p[++tot] = i;
for(int j=1;j<=tot && p[j] * i < N;j++){
v[p[j]*i] = 1;
if(i % p[j] == 0)break;
}
}
}
double dp(int x){
if(vis[x])return d[x];
vis[x] += 1;
int num = 0,cnt = 0;
for(int i=1;p[i] <= x;i++){
num ++;
if(x % p[i] == 0){
cnt ++;
d[x] += dp(x/p[i]);
}
}
//cout<<x << ' ' <<num << ' ' <<cnt<<endl;
d[x] += num;
d[x] /= cnt;
return d[x];
}
int main(){
primes();
cin>>T;
int cas = 0;
vis[1] = 1;d[1] = 0;
while(T--){
cin>>n;
printf("Case %d: %.6f\n",++cas,dp(n));
}
return 0;
}
4. 決鬥（UVA-1636）
首先在槍里裝一些子彈，然後扣了一槍，發現沒有子彈。你希望下一槍也沒有子彈，是應該直接再扣一槍（輸出SHOOT）呢，還是隨即轉一下再扣（輸出ROTATE)？如果這兩種策略下沒有子彈的概率相等，輸出EQUAL.
手槍里的子彈可以看成一個循環序列，開槍一次以後對準下一個位置。例如子彈序列為0011時，第一次開槍前一定在位置1或2（因為第一槍沒有子彈），因此開槍之後位於位置2或3。如果此時開槍，有一半的概率沒有子彈。序列長度為2~100。
#include <bits/stdc++.h>
using namespace std;
char s[110];
int a,b,len;
int main(){
while(cin>>s){
len = strlen(s);
s[len] = s[0];
a=0,b=0;
for(int i=0;i<len;i++){
if(s[i]=='0'){
a++;
if(s[i+1]=='0')b++;
}
}
int s1 = b*len,s2 = a*a;
if(s1>s2)puts("SHOOT");
else if(s1==s2)puts("EQUAL");
else puts("ROTATE");
}
return 0;
}
5. 奶牛和轎車(UVA-10491)
在a+b扇門，a扇後面是牛，b扇後面是車。在你選擇一扇門後，主持人為你打開另外c個有奶牛的門（\(1\le a\le 10000, 1\le b \le 10000, 0\le c < a\)），輸出此刻你選擇換門之後贏得車的概率。
#include <bits/stdc++.h>
using namespace std;
double a,b,c;
int main(){
while(cin>>a>>b>>c){
double res = (a*b+b*b-b)/(a+b)/(a+b-c-1);
printf("%.5f\n",res);
}
return 0;
}
6. 條件概率(UVA-11181)
有 n 個人準備去超市逛，其中第 i 個人買東西的概率是\(P_i\)。 逛完以後你得知有 r 個人買了東西。根據這一資訊，請計算每個人實際買了東西的概率。輸入 n (\(1\le n \le 20\)) 和 r (\(0\le r \le n\)), 輸出每個人買東西的概率。
#include <bits/stdc++.h>
using namespace std;
double a[30],sum,q[30],v[30],tot,cur;
int n,r;
void dfs(int x){
if(x==n+1){
if(tot==r){
//cout<<cur<<endl;
for(int i=1;i<=n;i++){
if(a[i])v[i] += cur;
}
sum+=cur;
}
return;
}
a[x] = 1;
tot++;
cur *= q[x];
dfs(x+1);
tot--;
cur /= q[x];
a[x] = 0;
cur *= (1-q[x]);
dfs(x+1);
cur /= (1-q[x]);
}
int main(){
int cas = 0;
while(cin>>n>>r){
if(n==0&&r==0)break;
cur = 1;sum = 0;memset(v,0,sizeof v);
for(int i=1;i<=n;i++)cin>>q[i];
dfs(1);
printf("Case %d:\n",++cas);
for(int i=1;i<=n;i++){
printf("%.6f\n",v[i]/sum);
}
}
}
7. 紙牌遊戲(UVA-1637)
36張牌分成9堆，每堆4張牌。每次可以拿走某兩堆頂部的牌，但需要點數相同。如果有多種拿法則等概率的隨機拿。例如，9堆頂部的牌分別為KS,KH,KD,9H,8S,8D,7C,7D,6H，則有5種拿法(KS,KH),(KS,KD),(KH,KD),(8S,8D),(7C,7D)，每種拿法的概率均為1/5。如果最後拿完所有牌則遊戲成功。按順序給出每堆的四張牌，求成功概率。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
char card[9][4][3];
map<vector<int>,double> d;
bool readcard()
{
for(int i=0;i<9;i++)
for(int j=0;j<4;j++)
if(scanf("%s",card[i][j])!=1) return false;
return true;
}
double dp(vector<int>& cnt,int c) //返回的是cnt這種狀態下成功的幾率
{
if(c==0) return 1; //已經成功了
if(d.count(cnt)!=0) return d[cnt]; //表明此狀態已經計算過了(記憶化搜索)
int tot=0; //記錄決策數
double sum=0;
for(int i=0;i<9;i++) if(cnt[i]) //第i堆牌的數量>0
for(int j=i+1;j<9;j++) if(cnt[j]) //第i堆牌的數量>0
if(card[i][cnt[i]-1][0]==card[j][cnt[j]-1][0]) ////第i堆牌的第一張和第j堆牌的第一張一樣
{
tot++;
cnt[i]--;cnt[j]--;
sum+=dp(cnt,c-2); //sum計算所有此狀態下成功的概率
cnt[i]++;cnt[j]++;
}
if(!tot) return d[cnt]=0; //這種狀態下不可能成功
else return d[cnt]=sum/tot ; //這種狀態下成功的幾率均分為tot份
}
int main()
{
while(readcard())
{
vector<int> cnt(9,4); //表示狀態;
d.clear();
printf("%.6lf\n",dp(cnt,36));
}
return 0;
}
8. 過河(UVA-12230)
你住在村莊A，每天需要過很多條河到另一個村莊B上班。B在A的右邊，所有的河都在中間。幸運的是，每條河上都有勻速移動的自動船，因此每當到一條河的左岸時，只需等船過來，載著你過河，然後在右岸下船。你很瘦，因此上船之後船速不變。
從A到B，平均情況下需要多久時間？假設在出門時所有船的位置都是均勻隨機分布的。如果位置不是在河的端點處，則朝向也是均勻隨機。在陸地上行走的速度為1
給出AB之間河的個數，長度D，以及每條河的左端離A的距離p，長度L和移動速度v，輸出A到B的數學期望。
#include <bits/stdc++.h>
using namespace std;
int n,D;
double p,L,v;
int main(){
int cas = 0;
while(cin>>n>>D){
if(n == 0 && D == 0)break;
double time = 0;
for(int i=1;i<=n;++i){
cin>>p>>L>>v;
time += 2.0 * L / v;
D -= L;
}
time += D;
printf("Case %d: %.3f\n\n",++cas,time);
}
return 0;
}
9. 糖果(UVA-1639)
有兩個盒子各有 n (\(n\le 2\times 10^5\))個糖，每天隨機選一個（概率分別為p，1-p），然後吃一顆糖。直到有一天，打開盒子一看，沒糖了！輸入n，p，求此時另一個盒子里糖的個數的數學期望。
#include <bits/stdc++.h>
using namespace std;
typedef long double db;
const int N = 4e5+10;
db loglc[N],p;
int n;
db logC(int n,int m){
return loglc[n] - loglc[m] - loglc[n-m];
}
int main(){
loglc[0] = log(1);
for(int i=1;i<N;i++){
loglc[i] = loglc[i-1] + log(i);
}
int cas = 0;
while(cin>>n>>p){
db res = 0;
for(int i=1;i<=n;i++){
db v1 = logC(2*n-i,n) + (n+1) * log(p) + (n-i) * log(1-p);
db v2 = logC(2*n-i,n) + (n+1) * log(1- p) + (n-i) * log(p);
res += i * (exp(v1) + exp(v2));
}
printf("Case %d: %.6Lf\n",++cas,res);
}
return 0;
}
10. 優惠券(UVA-10288)
大街上到處在賣彩票，一元錢一張。購買撕開它上面的錫箔，你會看到一個漂亮的圖案。圖案有n種，如果你收集到所有 n (\(n\le 33\))種彩票，就可以得大獎。請問，在平均情況下，需要買多少張彩票才能得到大獎呢？如 n = 5 時答案為137/12。
#include <bits/stdc++.h>
using namespace std;
int x;
long long a[35],b[35];
void creat(int n){
a[1] = 1;b[1] = 1;
for(int i=2;i<=n;i++){
int up = n,down = n - (i-1);
b[i] = b[i-1] * down + a[i-1] * up;
a[i] = a[i-1] * down;
long long gcd = __gcd(a[i],b[i]);
a[i] /= gcd;
b[i] /= gcd;
}
}
int count(long long x){
int res = 0;
while(x) x/=10,res++;
return res;
}
int main(){
while(cin>>x){
creat(x);
if(a[x] == 1)printf("%lld\n",b[x]);
else{
int pre = count(b[x] / a[x]);
int len = max(count(b[x] % a[x]),count(a[x]));
for(int i=0;i<pre+1;i++)printf(" ");
printf("%lld\n",b[x]%a[x]);
printf("%lld ",b[x] / a[x]);
for(int i=0;i<len;i++)printf("-");
printf("\n");
for(int i=0;i<pre+1;i++)printf(" ");
printf("%lld\n",a[x]);
}
}
return 0;
}
11. 危險的組合(UVA-580)
有一些裝有鈾（U）和鉛（L）得盒子，數量均足夠多。要求把n(\(n\le 30\)) 個盒子放在一行，但至少有3個U放在一起，有多少種方法？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p2[35];
ll f[35];
int main(){
p2[0] = 1;
for(int i=1;i<=30;i++)p2[i] = p2[i-1] * 2ll;
f[0] = f[1] = f[2] = 0;
for(int n=3;n<=30;n++){
for(int i=2;i <= n-2;i++){
f[n] += (p2[i-2] - f[i-2]) * p2[n-i-2];
}
f[n] += p2[n-3];
}
int n;
while(cin>>n){
if(n == 0)break;
cout<<f[n]<<endl;
}
return 0;
}
12. 比賽名次(UVA-12034)
A，B兩人賽馬，最終名次有3種可能：並列第一；A第一B第二；B第一A第二。輸入n(\(1\le n\le 1000\))，求n人賽馬時最終名次的可能性的個數除以10056的餘數
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 10056;
int f[N];
int C[N][N];
void init(){
C[0][0] = 1;
for(int i=1;i<N;i++){
C[i][0] = 1;
for(int j=1;j<=i;j++){
C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
}
}
}
int main(){
init();
f[0] = 1;
for(int i=1;i<N;i++){
for(int j=1;j<=i;j++){
f[i] = (f[i] + C[i][j] * f[i-j] %mod)%mod;
}
}
int T,n;cin>>T;
int cas = 0;
while(T--){
scanf("%d",&n);
printf("Case %d: %d\n",++cas,f[n]);
}
return 0;
}
13. 杆子的排列(UVA-1638)
有高為\(1,2,3,\cdots n\)的杆子各一根排成一行。從左邊能看到 \(l\) 根，從右邊能看到\(r\) 根，求有多少種可能。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,l,r;
ll d[22][22][22];
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&l,&r);
d[0][0][0] = 1;
d[1][1][1] = 1;
for(int k=2;k<=n;k++){
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
d[k][i][j] = d[k-1][i-1][j] + d[k-1][i][j-1] + d[k-1][i][j] * (k-2);
}
}
}
printf("%lld\n",d[n][l][r]);
}
return 0;
}
