UVa 12448 Casino Advantage

题目描述大西洋城的几家赌场正在考虑推出一款新游戏以吸引赌徒。游戏中一个球被随机滚入一个划分为NNN个槽位编号111至NNN的轮盘球停下的槽位编号即为该次滚动的结果。之后取出球再滚下一个总共滚动MMM次。玩家对MMM次滚动中出现的不同编号的个数KKK下注。赌场希望设定赔率使自身拥有微小优势因此需要知道某个投注成为赢注的概率。他们聘请了大西洋城数学家ACM\texttt{ACM}ACM来帮助计算给定N,M,KN, M, KN,M,K1≤N,M,K≤101 \le N, M, K \le 101≤N,M,K≤10求恰好出现KKK个不同值的概率。每次滚动独立且等概率落入任一槽位。输入格式输入第一行为一个整数TTTT≤1000T \le 1000T≤1000表示测试用例数。随后TTT行每行包含三个整数N,M,KN, M, KN,M,K。输出格式对每个测试用例输出最简分数形式的概率。格式为A/B其中AAA和BBB互质。若概率为000或111则仅输出整数0或1。保证约分后的分子分母均在323232位有符号整数范围内。样例输入4 3 1 2 2 5 2 3 5 3 4 6 2输出0 15/16 50/81 93/1024题目分析本题要求计算在MMM次独立均匀随机试验中恰好出现KKK个不同结果的概率。总样本空间大小为NMN^MNM每个球有NNN种等可能结果。有利事件定义为MMM个结果中恰好包含KKK个不同数字。考虑计数方法选择出现哪些数字从NNN个槽位中选出KKK个方案数为(NK)\binom{N}{K}(KN​)。分配MMM个球到这KKK个数字每个球只能落在选中的KKK个数字之一且每个数字至少出现一次否则实际不同数字个数会小于KKK。这等价于将MMM个有标号球放入KKK个有标号盒子不允许空盒。第二步的计数可以使用容斥原理。设AiA_iAi​表示第iii个盒子为空的事件则所有盒子非空的事件数为∑i0K(−1)i(Ki)(K−i)M \sum_{i0}^{K} (-1)^i \binom{K}{i} (K-i)^Mi0∑K​(−1)i(iK​)(K−i)M其中iii表示强制为空的盒子数剩下的(K−i)(K-i)(K−i)个盒子可以任意放置MMM个球每个球有(K−i)(K-i)(K−i)种选择总方案为(K−i)M(K-i)^M(K−i)M。因此有利事件总数为(NK)⋅∑i0K(−1)i(Ki)(K−i)M \binom{N}{K} \cdot \sum_{i0}^{K} (-1)^i \binom{K}{i} (K-i)^M(KN​)⋅i0∑K​(−1)i(iK​)(K−i)M概率即为该数除以NMN^MNM。边界条件若KNK NKN或KMK MKM显然概率为000因为不可能出现超过槽位数或超过球数的不同数字。由于N,M,KN, M, KN,M,K最大仅为101010所有幂和组合数均可用646464位整数精确计算不会溢出。最后通过约分得到最简分数。解题思路根据上述分析我们直接计算分子和分母然后约分输出。具体步骤如下预处理组合数由于N,K≤10N, K \le 10N,K≤10可以直接用递推公式或循环乘法除法计算(nk)\binom{n}{k}(kn​)保证结果为整数。计算幂函数实现快速幂或直接循环累乘计算aba^bab0≤a≤100 \le a \le 100≤a≤100≤b≤100 \le b \le 100≤b≤10结果在646464位范围内。计算容斥和循环iii从000到KKK累加(−1)i⋅(Ki)⋅(K−i)M(-1)^i \cdot \binom{K}{i} \cdot (K-i)^M(−1)i⋅(iK​)⋅(K−i)M。注意符号当iii为奇数时减偶数时加。计算分子分子 (NK)×\binom{N}{K} \times(KN​)×容斥和。计算分母分母 NMN^MNM。约分若分子为000直接输出0否则求分子和分母的最大公约数ggg分别除以ggg。输出若分母为111输出整数否则输出分子/分母。正确性说明容斥原理正确计数了MMM个球落入KKK个指定盒子且无空盒的方案数乘以(NK)\binom{N}{K}(KN​)即所有有利事件总数。总样本空间NMN^MNM正确表示所有等可能结果。约分得到最简分数符合题目要求。复杂度分析每个测试用例需要计算组合数、幂和容斥和循环次数为O(K)O(K)O(K)其中K≤10K \le 10K≤10因此单用例时间复杂度O(1)O(1)O(1)。总时间复杂度O(T)O(T)O(T)完全满足T≤1000T \le 1000T≤1000。空间复杂度O(1)O(1)O(1)。代码实现// Casino Advantage// UVa ID: 12448// Verdict: Accepted// Submission Date: 2026-06-23// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;// 计算组合数 C(n, k)llcomb(intn,intk){if(k0||kn)return0;if(kn-k)kn-k;ll res1;for(inti1;ik;i){resres*(n-i1)/i;}returnres;}// 快速幂计算 a^bllpowll(ll a,intb){ll res1;while(b){if(b1)res*a;a*a;b1;}returnres;}// 最大公约数llgcdll(ll a,ll b){while(b){ll ta%b;ab;bt;}returna;}intmain(){intT;scanf(%d,T);while(T--){intN,M,K;scanf(%d %d %d,N,M,K);// 不可能的情况if(KN||KM){printf(0\n);continue;}// 计算容斥和sum_{i0}^{K} (-1)^i * C(K,i) * (K-i)^Mll sum0;for(inti0;iK;i){ll termcomb(K,i)*powll(K-i,M);if(i1)sum-term;elsesumterm;}// 分子 C(N,K) * sumll numeratorcomb(N,K)*sum;ll denominatorpowll(N,M);// 约分if(numerator0){printf(0\n);continue;}ll ggcdll(numerator,denominator);numerator/g;denominator/g;if(denominator1)printf(%lld\n,numerator);elseprintf(%lld/%lld\n,numerator,denominator);}return0;}总结本题是一道基础的概率计数题核心在于利用容斥原理计算“恰好出现KKK个不同值”的方案数。由于数据范围极小直接计算组合数和幂即可无需优化。关键点在于正确识别有利事件的结构先选数字再分配球。容斥原理的应用处理“至少出现一次”的约束。分数约分和特殊输出格式000和111单独输出。本题也提醒我们即使题目背景复杂但若能转化为经典组合计数模型就能快速解决。在编程实现时注意使用646464位整数防止中间结果溢出并利用最大公约数化简分数。