高端品牌网站建设兴田德润怎么联系,上市公司做网站,贵阳网络推广优化,怎么分析一个网站概率论专题 目录 MT2226 抽奖概率MT2227 饿饿#xff01;饭饭#xff01;MT2228 甜甜花的研究MT2229 赌石MT2230 square MT2226 抽奖概率 难度#xff1a;黄金 时间限制#xff1a;1秒 占用内存#xff1a;128M 题目描述 小码哥正在进行抽奖#xff0c;箱子里有…概率论专题 目录 MT2226 抽奖概率MT2227 饿饿饭饭MT2228 甜甜花的研究MT2229 赌石MT2230 square MT2226 抽奖概率 难度黄金 时间限制1秒 占用内存128M 题目描述 小码哥正在进行抽奖箱子里有一红一白两小球每次摸出一个球摸到红球中奖 如果中奖就不再继续抽奖如果未中奖 (摸到白球)则往箱子里补充一个白球 (摸出的白球不放回)继续抽奖直到中奖或者达到最大抽奖次数。 假设至多能抽奖 M M M 次求当停止抽奖时(中奖球数/摸出总球数) 的期望。 格式 输入格式一行一个整数 M M M。 输出格式保留到小数后六位。 样例 1 输入 4 输出 0.682292 备注 其中 1 ≤ M ≤ 10000 1\le M\le10000 1≤M≤10000。 相关知识点概率论 题解 箱子中只有一个红球和一个白球因此第一次抽取时抽到红球和抽到白球的概率各占一半。接下来对该箱子进行盲抽如果抽出红色则停止抽奖如果抽到白色则重新放入一个白球已被抽出的白球不放回。这就是说对该箱子的每一次抽取其内部总是含有一个红球和一个白球。因此这个模型实际上是一个 p 1 2 p\frac{1}{2} p21 的伯努利概型。本题要求的是停止抽奖时 “中奖球数/摸出总球数” 的数学期望。从理论上说“抽到奖时摸出的总球数” 可以取到无穷大即永远抽不到。因此本题限制假设最多能抽 M M M 次。
注意到题目要求的是 “中奖球数/摸出总球数” 的期望而在停止抽奖时即抽到奖或达到最大抽奖次数时“中奖球数” 始终为1。因此我们的主要目标是算出停止抽奖时其当前 “摸出的总球数”。显然这个值可取 1、2、……、M。具体来说这些取值与其对应的概率如下
抽 1 次中奖的概率 1 2 \frac{1}{2} 21第一次摸到红球中奖球数/摸出总球数 1 1 \frac{1}{1} 11 1抽 2 次中奖的概率 1 2 × 1 2 1 2 2 \frac{1}{2}\times\frac{1}{2}\frac{1}{2^2} 21×21221第一次摸到白球第二次摸到红球中奖球数/摸出总球数 1 2 \frac{1}{2} 21 抽 3 次中奖的概率 1 2 2 × 1 2 1 2 3 \frac{1}{2^2}\times\frac{1}{2}\frac{1}{2^3} 221×21231前两次摸到白球第三次摸到红球中奖球数/摸出总球数 1 3 \frac{1}{3} 31 ……抽 M M M 次中奖的概率 1 2 M − 1 × 1 2 1 2 M \frac{1}{2^{M-1}}\times\frac{1}{2}\frac{1}{2^M} 2M−11×212M1前 M − 1 M-1 M−1 次摸到白球第三次摸到红球中奖球数/摸出总球数 1 M \frac{1}{M} M1 。
我们知道离散变量的期望公式为 E ( X ) ∑ x x ⋅ P ( X x ) E\left(X\right)\sum_xx·P(Xx) E(X)x∑x⋅P(Xx)
其中 P ( X x ) P\left(Xx\right) P(Xx) 表示变量取 x x x 时的概率。在本题中 x x x 的取值范围即为 1 1 \frac{1}{1} 11、 1 2 \frac{1}{2} 21、……、 1 M \frac{1}{M} M1其对应的 P ( X x ) 1 2 x P\left(Xx\right)\frac{1}{2^x} P(Xx)2x1。因此本题所求期望的取值即为 E ( X ) ∑ x x ⋅ P ( X x ) 1 1 × 1 2 1 2 × 1 2 2 ⋯ 1 M × 1 2 M E\left(X\right)\sum_xx·P(Xx)\frac11×\frac12\frac12×\frac{1}{2^2}⋯\frac1M×\frac{1}{2^M} E(X)x∑x⋅P(Xx)11×2121×221⋯M1×2M1
基于此可直接写出求解本题的完整代码
/*MT2226 抽奖概率 离散变量的期望公式
*/
#includebits/stdc.h
using namespace std;
// 求“中奖球数 / 摸出总球数” 的期望
float getException(int m){int i 1;float ans 0;while(im){ans 1.0/(i*pow(2,i));i;}return ans;
}
int main()
{
// 获取输入int m; cinm;// 格式化输出期望 printf(%.6f,getException(m));return 0;
} MT2227 饿饿饭饭 难度黄金 时间限制1秒 占用内存128M 题目描述 嗯哼小码哥在新的一年里不会忘记身为干饭人的初心众所周知小码哥非常不喜欢一直吃同样的东西但由于理想与现实的差距食堂在这 n n n 天里只会供应种 k k k 餐食。 在一天吃 3 餐的情况下前 w w w 天一共 w × 3 w\times3 w×3 顿饭小码哥不希望有任何一顿重复。现在请问食堂有多少种方案可以满足超级可爱乖巧的小码哥的需要。 格式 输入格式一行三个整数 n , k , w n,\ k,\ w n, k, w 表示 n n n 天内食堂只会供应 k k k 种餐食 w w w 的意义详见题面。 输出格式输出一行一个数表示满足小码哥需要的方案数。 样例 1 输入 5 4 1 输出 24 备注 其中 1 ≤ n , w , k ≤ 12 1\le n,\ w,\ k\le12 1≤n, w, k≤12。 相关知识点排列组合 题解 对题目的简化描述如下食堂提供 n n n 种餐食小码哥要吃 m m m 顿饭求能使小码哥不吃重的进餐方案数。
这显然是一个排列问题。例如当 n 4 , m 3 n4,\ m3 n4, m3 时为使小码哥不吃重其选择餐食的思路如下
第一顿小码哥可任意选择餐食共 4 种方案第二顿小码哥只能在剩下 3 种餐食中选择第三顿小码哥只能在剩下 2 种餐食中选择。
于是可得到小码哥不吃重的进餐方案数为4×3×224 种。
下面给出排列数的计算公式 A n m n × ( n − 1 ) × … × ( n − m 1 ) n ! ( n − m ) ! A_n^mn\times\left(n-1\right)\times\ldots\times(n-m1)\frac{n!}{\left(n-m\right)!} Anmn×(n−1)×…×(n−m1)(n−m)!n!
基于此可得到求解本题的完整代码
/*MT2227 饿饿饭饭 排列问题从 k 个不同物品中选 3*w 个不同物品的方案数
*/
#includebits/stdc.h
using namespace std; typedef long long ll;
// 从 n 中选取 m 个物品的排列数
ll A(ll n, ll m){ll ans 1;for(int in; m1; i--, m--){ans * i;}return ans;
}int main()
{// 获取输入int n,k,w; cinnkw;// 格式化输出总方案数coutA(k,3*w)endl; return 0;
} MT2228 甜甜花的研究 难度黄金 时间限制1秒 占用内存128M 题目描述 小码哥酷爱研究植物他对甜甜花的研究无人能及可他仍然在不断研究着。现在小码哥有 n n n 粒甜甜花的种子每一粒种子都能长出不同的甜甜花由于种子实在太多小码哥一个人实在无法照料于是他雇佣了 m m m 位种植能手第 i i i 个人能照料 a i {\ a}_{i\ } ai 株甜甜花请问小码哥有多少种分配方式将这些种子分配出去 格式 输入格式第一行输入以空格隔开的两个整数 N N N 和 K K K 第二行输入 m m m 个正整数分别代表 a i {\ a}_{i\ } ai 。 输出格式输出一个整数表示方法个数 由于结果可能很大须将结果对 12520 取模。 样例 1 输入 5 2 3 1 输出 20 备注 其中 n ≤ 10 4 , m ≤ 100 , a i ≤ 100 n\le{10}^4,\ m\le100,\ {\ a}_{i\ }\le100 n≤104, m≤100, ai ≤100 数据保证种子有剩余。 相关知识点排列组合 题解 对题目的简化描述如下现有 n n n 粒不同种子 m m m 个不同盒子各盒子的容量分别为 a 1 , a 2 , … , a m a_1, a_2, … ,a_m a1,a2,…,am。在保证种子数大于所有盒子容量之和的前提下问有多少种不同的分装方案。
这显然是一个组合问题。例如当 n 8 , m 3 ( a 1 1 , a 2 2 , a 3 3 ) n8,m3\ (a_11,a_22,a_33) n8,m3 (a11,a22,a33) 时对这些种子的分装如下
盒子 1在 8 8 8 粒种子中选择 1 1 1 粒共 C 8 1 8 C_8^18 C818 种方案盒子 2在剩下 8 − 1 7 8-17 8−17 粒种子中选择 2 粒共 C 7 2 21 C_7^221 C7221 种方案盒子 3在剩下 7 − 2 5 7-25 7−25 粒种子中选择 3 粒共 C 5 3 10 C_5^310 C5310 种方案。
因此总的分装方案数有 8×21×101680 种。
下面给出组合数的计算公式 C n m n × ( n − 1 ) × … × ( n − m 1 ) m × ( m − 1 ) × … × 1 n ! m ! × ( n − m ) ! C_n^m\frac{n\times(n-1)\times\ldots\times(n-m1)}{m\times(m-1)\times\ldots\times1}\frac{n!}{m!\times(n-m)!} Cnmm×(m−1)×…×1n×(n−1)×…×(n−m1)m!×(n−m)!n!
需要注意一点组合数是一个关于 n n n 和 m m m 变化非常大的函数因此实现时最好采取较大的数据范围和一定的优化方式如一边除一边乘。下面直接给出基于以上思路得到的完整代码
/*MT2228 甜甜花的研究组合问题
*/
#includebits/stdc.h
using namespace std; const int MOD 12520;
const int M 105;
int ary[M];typedef long long ll;
// 从 n 中选取 m 个物品的组合数
ll C(ll n, ll m){ll ans 1;for(ll i1; im; i){// 边乘边除 ans ans*(n-mi)/i;}return ans;
}// 对种子的分配过程
int Distribute(int n, int m){ll ans 1;for(int i0;im; i){ans * C(n, ary[i]);n - ary[i];}return ans%MOD;
}int main()
{// 获取输入int n, m; cinnm;for(int i0; im; i)cinary[i];// 输出期望 coutDistribute(n, m)endl;return 0;
} MT2229 赌石 难度黄金 时间限制1秒 占用内存128M 题目描述 富饶的璃月街道上有一家石料店店主小码哥是个精明的商人为了使他的赌石生意更加红火他根据赌徒的心理设计了一个有趣的买卖规则他在店铺的两边放了个小桶一个桶里有 n n n 个红球另一个有 n n n 个蓝球。每一批 2 n 2n 2n 个璞石与这些球一一对应对每个来买璞石的客户小码哥都会让他们在原地闭眼旋转数圈后走向一个小桶若拿到蓝球则可免费获得一块石头但若拿到红球则需要付出两倍的价钱。 假设每个人每次拿到蓝球和红球的概率相同现在请你求出一个桶里没球而另一个桶里还剩两个球的概率精确到小数点后四位。 格式 输入格式输入一个正整数代表这批璞石的个数不大于2500且保证为偶数。 输出格式输出一个四位小数代表所求答案。 样例 1 输入 256 输出 0.9500 相关知识点排列组合 题解 对题目的简化描述如下有两个盒子一个盒子盛有 n n n 个蓝球一个盒子盛有 n n n 个红球。现对这两个盒子进行随机抽取求最终场上出现一个盒子剩 2 个球而另一个没有球的概率。
这道题并没有说停止摸球的条件比如当出现一个盒子没有球而另一个盒子还剩 3、4、……、 n n n 个球时要如何算而是直接问出现某种情况的概率。从官方给出的答案看其对本题模型做出了以下归结即最终只会存在 3 种情况作为结束时的状态如下表所示。 这也就是说本题默认将 “一个盒子没有球而另一个盒子还剩 3、4、……、 n n n 个球” 的情形最终归结为 “一个盒子剩 2 个球另一个没有球” 这种情况。即认为系统会一直摸球直到摸到 2 n − 2 2n-2 2n−2 个球为止当出现某个盒子已经没有球时下一次摸球就只会从剩余有球的盒子里摸取。下面我们基于这一设定进行分析。
题目要求的是 “一个盒子剩 2 个球另一个没有球” 的概率而从上面的分析可知这类情况实际上包含了许多状态即一个盒子没有球而另一个盒子有2、3、4、……时都为符合要求的状态。这时可以通过计算这些状态的出现概率得到通项然后再以级数的方式进行归结。这种方法有一定的难度并且过于繁琐。在概率论里对此类题更常用的处理方式是通过计算对立事件的概率进而得到原事件的概率。在本题中从两个各含 n n n 个球的盒子中随机摸 2 n − 2 2n-2 2n−2 个球原事件 “一个盒子没有球而另一个盒子还剩 2 个球” 的对立事件为 “两个盒子各剩下一个球”。于是接下来我们分析 “两个盒子各剩一个球的概率”。
由于摸出球的总数为 2 n − 2 2n-2 2n−2 如果要求最终两个盒子各剩一个球那就要求摸出的这 2 n − 2 2n-2 2n−2 个球里有一半的球来自指定盒子。由于题目说了每个人每次拿到蓝球和红球的概率相等因此每一次摸球时此球为蓝色或红色的概率是相等的均为 1 2 \frac{1}{2} 21 。基于此可知摸出 2 n − 2 2n-2 2n−2 个球里 n − 1 n-1 n−1 个球同色的概率为 p C 2 n − 2 n − 1 ( 1 2 ) n − 1 ( 1 2 ) n − 1 C 2 n − 2 n − 1 ( 1 2 ) 2 n − 2 pC_{2n-2}^{n-1}\left(\frac{1}{2}\right)^{n-1}\left(\frac{1}{2}\right)^{n-1}C_{2n-2}^{n-1}\left(\frac{1}{2}\right)^{2n-2} pC2n−2n−1(21)n−1(21)n−1C2n−2n−1(21)2n−2
根据该概率值可以得到其对立事件的概率为 1 − p 1 − C 2 n − 2 n − 1 ( 1 2 ) 2 n − 2 1-p1-C_{2n-2}^{n-1}\left(\frac{1}{2}\right)^{2n-2} 1−p1−C2n−2n−1(21)2n−2
这便是本题的答案。
注意到一件事题目给出的取值范围为 2 n ≤ 2500 2n\le2500 2n≤2500即 n n n 最大可取到 1250这样的范围在求组合数时必定存在过于庞大的数这意味着即使用 long double 型也可能会越界。因此我们必须简化对该值的求解即考虑拆分 C 2 n − 2 n − 1 ( 1 2 ) 2 n − 2 C_{2n-2}^{n-1}\left(\frac{1}{2}\right)^{2n-2} C2n−2n−1(21)2n−2 使得计算过程能被优化为较小的数之间的四则运算即找到一个通项式。 C 2 n − 2 n − 1 ( 1 2 ) 2 n − 2 ( 2 n − 2 ) ! ( n − 1 ) ! ( n − 1 ) ! × ( 1 4 ) n − 1 ( 2 n − 2 ) × ( 2 n − 1 ) × … × 1 ( n − 1 ) ! ( n − 1 ) ! × 1 4 n − 1 ( 2 n − 2 ) × ( 2 n − 1 ) × … × n ( n − 1 ) ! × 1 4 n − 1 ( 2 n − 2 ) × ( 2 n − 1 ) × … × n 4 n − 1 × [ ( n − 1 ) × ( n − 2 ) × … × 1 ] ( n − 1 n − 1 ) × ( n − 1 n − 2 ) × … × ( n − 1 1 ) 4 ( n − 1 ) × 4 ( n − 2 ) × … × 4 ( 1 ) ∏ i 1 n − 1 ( n − 1 i ) 4 i \begin{align} \nonumber C_{2n-2}^{n-1}\left(\frac{1}{2}\right)^{2n-2} \\ \nonumber \frac{\left(2n-2\right)!}{(n-1)!(n-1)!}\times\left(\frac{1}{4}\right)^{n-1} \\ \nonumber \frac{\left(2n-2\right)\times\left(2n-1\right)\times\ldots\times1}{(n-1)!(n-1)!}\times\frac{1}{4^{n-1}} \\ \nonumber \frac{\left(2n-2\right)\times\left(2n-1\right)\times\ldots\times n}{(n-1)!}\times\frac{1}{4^{n-1}} \\ \nonumber \frac{\left(2n-2\right)\times\left(2n-1\right)\times\ldots\times n}{4^{n-1}\times\left[(n-1)\times\left(n-2\right)\times\ldots\times1\right]} \\ \nonumber \frac{\left(n-1n-1\right)\times\left(n-1n-2\right)\times\ldots\times(n-11)}{4(n-1)\times4\left(n-2\right)\times\ldots\times4(1)} \\ \nonumber \prod_{i1}^{n-1}\frac{\left(n-1i\right)}{4i} \end{align} C2n−2n−1(21)2n−2(n−1)!(n−1)!(2n−2)!×(41)n−1(n−1)!(n−1)!(2n−2)×(2n−1)×…×1×4n−11(n−1)!(2n−2)×(2n−1)×…×n×4n−114n−1×[(n−1)×(n−2)×…×1](2n−2)×(2n−1)×…×n4(n−1)×4(n−2)×…×4(1)(n−1n−1)×(n−1n−2)×…×(n−11)i1∏n−14i(n−1i)
如此就将原来求组合数的过程转换为求若干子式小范围的乘积。
于是得到 “一个盒子没有球而另一个盒子还剩2个球” 的概率为 1 − ∏ i 1 n − 1 ( n − 1 i ) 4 i 1-\prod_{i1}^{n-1}\frac{\left(n-1i\right)}{4i} 1−i1∏n−14i(n−1i)
下面给出基于以上思路得到的完整代码
/*MT2229 赌石
*/
#includebits/stdc.h
using namespace std; // 从两个含有 n 个球的桶中取数最终情况为 0-2 的概率
double getProbability(int n)
{double ans 1;for(int i1; in; i)ans * (n-1i)/(i*4.0);return 1-ans;
} int main()
{// 获取输入 int n; cin n;// 格式化输出 printf(%.4lf\n, getProbability(n/2));return 0;
} MT2230 square 难度钻石 时间限制3秒 占用内存128M 题目描述 在一个 m × n m×n m×n 的矩阵上小码哥在左下角的顶点出现了他只能沿着路径向上或者向右走他的目标是 “蠕动” 到右上角的顶点问他有多少路径可以选择。嗯这个、这个、这个似乎地球人都知道怎么做但是请注意我有个条件没给呢 m m m 和 n n n 现在的最大范围是 50000这可怎么办仔细想想吧。 格式 输入格式只有一行包含两个整数 m m m 和 n n n其均不小于 4上限均为 50000。 输出格式由于最后的答案数目过大所以只检查后 100 位输出时每行十个数字没空格间隔共十行如果答案位数没超过 100 位则需要在空位上补 0。 样例 1 输入 7 4 输出 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000330 相关知识点排列组合 题解 求从矩阵左下角到右上角的行走方案数每次只能移动一个单位是一个经典的迷宫问题。解决这个问题最简单的办法是动态规划因为任意非边缘这里的边缘主要是指与初始位置相邻的两侧如本题中就是左侧和下侧位置的前一个位置必定是左或下因此可以很轻松地得到状态转移方程为 d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i ] [ j − 1 ] dp[i][j]dp[i-1][j]dp[i][j-1] dp[i][j]dp[i−1][j]dp[i][j−1]
由于这种行走方式随矩阵规格变化非常剧烈因此大多数题目都要求记录一个对指定数的模而本题则要求记录所有行走方式总量的末尾指定长度数串。在这样的要求下递推求解的思路变得不再适用。 对于走格子矩阵问题假设其规格为 m × n m\times n m×n 表示横向有 m m m 条路径纵向有 n n n 条路径首先要肯定一点从左下角走到右上角每次移动一个单位且不可倒退其一定会走 m n mn mn 步其中 m m m 步向右 n n n 步向上。而各移动方案之间的差异无非就是 “向上” 和 “向右” 的次序不同。例如对于一个 2 × 3 2\times3 2×3 的矩阵其行走方案根据 “向上” 和 “向右” 次序的不同可分为以下 10 种不同的行走方案 → → ↑ ↑ ↑ → ↑ → ↑ ↑ → ↑ ↑ → ↑ → ↑ ↑ ↑ → ↑ → → ↑ ↑ ↑ → ↑ → ↑ ↑ → ↑ ↑ → ↑ ↑ → → ↑ ↑ ↑ → ↑ → ↑ ↑ ↑ → → →→↑↑↑ \\ →↑→↑↑ \\ →↑↑→↑ \\ →↑↑↑→ \\ ↑→→↑↑ \\ ↑→↑→↑ \\ ↑→↑↑→ \\ ↑↑→→↑ \\ ↑↑→↑→ \\ ↑↑↑→→ \\ →→↑↑↑→↑→↑↑→↑↑→↑→↑↑↑→↑→→↑↑↑→↑→↑↑→↑↑→↑↑→→↑↑↑→↑→↑↑↑→→
因此走格子矩阵问题也能通过求组合数得到此时其含义即为 “在 m n mn mn 步中选 n n n 步向上走”或 “在 m n mn mn 步中选 m m m 步向右走”的总方案数。即 C m n n C_{mn}^n Cmnn 或 C m n m C_{mn}^m Cmnm。另一方面本题中的 m m m 和 n n n 最大可取到 5000这对组合数而言是一个十分庞大的数据任何数据类型都无法存储下就算采取 “边乘边除” 的策略也没有一个数据类型能对中间结果进行存储因此我们现在的问题是如何实现大范围的组合数求解
在前面质数章节曾提到任意一个大于 1 的正整数 n u m num num 都可以分解为若干质因数的乘幂之积 n u m p 1 α 1 × p 2 α 2 × … × p k α k nump_1^{\alpha_1}\times p_2^{\alpha_2}\times\ldots\times p_k^{\alpha_k} nump1α1×p2α2×…×pkαk
基于此我们可将求组合数的过程进行转换每对一个数进行乘法运算时不直接算出乘积而是记录当前乘数可被划分为哪些质因数之积并对这些质因数进行相应记录。显然对组合数分子部分的阶乘要累加记录各乘数的质因数对组合数分母部分的阶乘要累减记录各乘数的质因数。例如求组合数 C 20 5 C_{20}^5 C205 的过程如下设质因数数组为 factor[ ]{0} C 20 5 20 × 19 × 18 × 17 × 16 5 × 4 × 3 × 2 × 1 C_{20}^5\frac{20\times19\times18\times17\times16}{5\times4\times3\times2\times1} C2055×4×3×2×120×19×18×17×16
阶段一统计分子部分的阶乘。
分解 20 2 2 × 5 1 202^2\times5^1 2022×51 于是有factor[2]{2}factor[5]{1}分解 19 19 1 19{19}^1 19191于是有factor[19]{1}分解 18 2 1 × 3 2 182^1\times3^2 1821×32于是有factor[2]{3}factor[3]{2}分解 17 17 1 17{17}^1 17171于是有factor[17]{1}分解 16 2 4 162^4 1624于是有factor[2]{7}。
阶段二统计分母部分的阶乘。
分解 5 5 1 55^1 551 于是有factor[5]{0}分解 4 2 2 42^2 422 于是有factor[2]{5}分解 3 3 1 33^1 331 于是有factor[3]{1}分解 2 2 1 22^1 221 于是有factor[2]{4}。
两个阶段结束后最终得到的质因子数组内容为factor[3]{1}、factor[5]{1}、factor[17]{1}、factor[19]{1}。将这些质因数按其对应次数进行叠乘即得到 C 20 4 C_{20}^4 C204 的值 2 4 × 3 1 × 17 1 × 19 1 15504 2^4\times3^1\times{17}^1\times{19}^115504 24×31×171×19115504 。
采取这样的方式可将组合数在计算过程中涉及到的阶乘运算巧妙地转换为若干个质因数的乘积过程从而避免了组合数在大数情况下容易越界的风险。另一方面如果直接采取大数运算的方式求组合数会出现大数除法的情况采取质因数分解的办法可避免出现除法。
由于前面已经给出了 质因数分解 以及 大数乘法 的相关实现在此就直接给出基于以上思路得到的求解本题目的完整代码
/*MT2230 squre求组合数 、质因数分解、大数乘法
*/
#include bits/stdc.h
using namespace std;
const int N 1e6 7;
const int M 100;
// 质因数数组
int factor[N];
// 大数乘法的结果数组
int ans[M5];
// 大数乘法单精度*高精度
void multi(int x)
{// 将原数组中的各数与指定数相乘for(int i1; iM; i)ans[i] * x;// 进位处理 for(int i 1; i M; i) {ans[i 1] ans[i] / 10;ans[i] % 10;}
}
int main()
{int m, n, x;cinmn;// 尽可能减少计算量 if(mn) swap(m, n);// 记录 C(m, n) 分子 n*(n-1)*…*(n-m1) 的质因数 for(int i0; im; i) {x mn-i;for(int j 2; jx/j; j) {while(x%j 0) {x / j;factor[j];}}if(x ! 1)factor[x];}// 记录 C(m, n) 分母 m! 的质因数约去 for(int i1; im; i) {x i;for(int j 2; jx/j; j) {while(x%j 0) {x / j;factor[j]--;}}if(x ! 1)factor[x]--;}// 遍历保存的质因数通过大数乘法统计结果 ans[1] 1;for(int i1; i N; i) {while(factor[i]) {multi(i);factor[i]--;}}// 格式化输出 for(int iM; i1; i--) {coutans[i];if(i%10 1) coutendl;}return 0;
}END
