新闻详情

新闻详情

首页 / 资讯中心 / 详情

UVa 12448 Casino Advantage

发布时间:2026/9/29 2:00:29来源:尧图网络
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位整数防止中间结果溢出并利用最大公约数化简分数。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

AIGC智能体(本质、结构以及如何构建)培训P 2026/9/29 2:00:25

AIGC智能体(本质、结构以及如何构建)培训P

本 130 页 PPT 适配大模型、AI 智能体类咨询方案与企业内部 AI 培训课件。系统讲解 AIGC 智能体核心本质、任务环境分类、技术架构,拆解 LLM 智能体感知‑记忆‑规划‑执行完整工作闭环。覆盖不同类型智能体原理、构建方法,结合行业调研,梳理…

阅读更多 →
电缆损伤检测数据集 | 7800张YOLO电力巡检数据集 2026/9/29 2:00:25

电缆损伤检测数据集 | 7800张YOLO电力巡检数据集

电缆损伤检测数据集 | 7800张YOLO电力巡检数据集 适用于输电线路巡检、无人机巡线与目标检测研究 一、数据集概述 本数据集针对电缆常见损伤类型进行标注,共包含约7800张高质量标注图像,专为电缆表面损伤检测模型训练、验证与测试设计。电缆作为电力传…

阅读更多 →
判断与循环 2026/9/29 2:00:18

判断与循环

流程控制语句 1. 顺序结构 2. 分支语句 if 语句 if 语句的第一种格式: if (关系表达式) {语句体; }关系表达式为真则执行语句体,否则不执行。 注意事项: 大括号的开头可以另起一行书写,但建议写在第一行的末尾。在语句体中&#x…

阅读更多 →
ESP32-CAM图像传输实战:从硬件接线到M-JPEG流稳定推送 2026/9/29 2:00:18

ESP32-CAM图像传输实战:从硬件接线到M-JPEG流稳定推送

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
电机控制进阶:从直流电机到FOC的完整学习路径 2026/9/29 2:00:18

电机控制进阶:从直流电机到FOC的完整学习路径

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
工控系统安全:从PLC确定性原理到现场可执行的三层防御 2026/9/29 2:00:18

工控系统安全:从PLC确定性原理到现场可执行的三层防御

1. 这不是演习:当工厂的PLC突然“听不懂人话”,我们才真正看清工业控制系统安全的底牌“全球视野下的工业控制系统安全,15大震惊全球工业安全事件带来的警钟长鸣”——这个标题里藏着的不是危言耸听的新闻稿,而是过去二十年里&…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉