「一本通 6.6 例 3」组合 - 省实信息学奥赛 - 在线练习

广东实验中学信息学奥赛评测系统

问题 2930. -- 「一本通 6.6 例 3」组合

2930: 「一本通 6.6 例 3」组合

时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>给出组合数 <span class="katex"><span class="katex-mathml">C(n,m)C(n,m)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">C</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mclose">)</span></span></span></span> 表示从 <span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个元素中选出 <span class="katex"><span class="katex-mathml">mm</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个元素的方案数。例如 <span class="katex"><span class="katex-mathml">C(5,2)=10,C(4,2)=6C(5,2) = 10, C(4,2) = 6</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">C</span><span class="mopen">(</span><span class="mord mathrm">5</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mclose">)</span><span class="mrel">=</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.07153em;">C</span><span class="mopen">(</span><span class="mord mathrm">4</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mclose">)</span><span class="mrel">=</span><span class="mord mathrm">6</span></span></span></span>。可是当 <span class="katex"><span class="katex-mathml">n,mn,m</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mpunct">,</span><span class="mord mathit">m</span></span></span></span> 比较大的时候，<span class="katex"><span class="katex-mathml">C(n,m)C(n,m)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">C</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mclose">)</span></span></span></span> 很大。于是 xiaobo 希望你输出 <span class="mjx-chtml"><span class="mjx-math"><span class="mjx-mrow"><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.519em; padding-bottom:0.298em; padding-right:0.045em;">C</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">(</span></span><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">n</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.144em; padding-bottom:0.519em;">,</span></span><span class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">m</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">)</span></span><span class="mjx-mo" style="padding-left:0.278em; padding-right:0.278em;"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.372em; padding-bottom:0.372em;">mod</span></span><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.446em;">p</span></span></span></span></span> 的值。</p>
</div></div>

输入

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>输入数据第一行是一个正整数 <span class="katex"><span class="katex-mathml">TT</span><span class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">T</span></span></span></span>，表示数据组数；</p>
<p>接下来是 <span class="katex"><span class="katex-mathml">TT</span><span class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">T</span></span></span></span> 组数据，每组数据有 <span class="katex"><span class="katex-mathml">33</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">3</span></span></span></span> 个正整数 <span class="katex"><span class="katex-mathml">n,m,pn,m,p</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mpunct">,</span><span class="mord mathit">p</span></span></span></span>。</p>
</div></div>

输出

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>对于每组数据，输出一个正整数，表示 <span class="mjx-chtml"><span class="mjx-math"><span class="mjx-mrow"><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.519em; padding-bottom:0.298em; padding-right:0.045em;">C</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">(</span></span><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">n</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.144em; padding-bottom:0.519em;">,</span></span><span class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">m</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">)</span></span><span class="mjx-mo" style="padding-left:0.278em; padding-right:0.278em;"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.372em; padding-bottom:0.372em;">mod</span></span><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.446em;">p</span></span></span></span></span> 的结果。</p>
</div></div>

提示

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><h4>样例输入</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">2
5 2 3
5 2 61</code></pre></div>
<h4>样例输出</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">1
10</code></pre></div>
</div></div>

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>对于所有数据，<span class="katex"><span class="katex-mathml">T≤100Tle 100</span><span class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.8193em; vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span></span></span></span>，<span class="katex"><span class="katex-mathml">1≤m≤n≤1091le mle nle 10^9</span><span class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:0.950078em; vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">m</span><span class="mrel">≤</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord"><span class="mord mathrm">0</span><span class="vlist"><span style="top:-0.363em; margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">9</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>，<span class="katex"><span class="katex-mathml">m≤104mle 10^4</span><span class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:0.950078em; vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord"><span class="mord mathrm">0</span><span class="vlist"><span style="top:-0.363em; margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">4</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>，<span class="katex"><span class="katex-mathml">m<p<109mlt plt 10^9</span><span class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.008548em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span><span class="mrel"><</span><span class="mord mathit">p</span><span class="mrel"><</span><span class="mord mathrm">1</span><span class="mord"><span class="mord mathrm">0</span><span class="vlist"><span style="top:-0.363em; margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">9</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>，<span class="katex"><span class="katex-mathml">pp</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">p</span></span></span></span> 是素数。</p>
</div></div>

标签

一本通提高篇 10228 组合计数 Lucas 定理

[上一题][提交][讨论版][状态][下一题]

OI模式 | OJ模式 | 笔记本 | 如果发现题目有问题，请联系管理员：crxis@qq.com OIER
All Copyright Reserved 2010-2015 广东实验中学信息学奥赛评测系统 TEAM