UVA10375 Choose and divide 组合数

时间：2025年09月23日

来源：yalanda

编辑：本站小编

小编在这里给大家带来UVA10375 Choose and divide 组合数，本文共5篇，希望大家喜欢!本文原稿由网友“yalanda”提供。

篇1：UVA10375 Choose and divide 组合数

题意很简单，求两个组合数相除，数字有点大，想要直接求是不可能的，只能想办法化简或者其它办法，基础可能打的不是很结实，一开始想不出，有点想要把除法变成乘法，然后约分，这样不太现实，万一p,q很大，r,s很小还是有可能超的，感觉这道题目比较好的，思路有点活，最后想出来还是觉得题目比较奇妙的，题目给的

C(m,n) = -------------

n!(m-n)!

事实上在看白书的时候里面数学基础知识那里有个介绍的，还可以写成

m*(m-1)*(m-2)...(m-n+1)

C(m,n) = ------------------------------------

然后进一步我们可以发现，观察一下，分母阶乘化简开来，项数为n项，分子我们仔细看看，从m乘到(m-n+1)，实际上项数（m-(m-n)）也就是n项，意思是这个分式的分子项数和分母项数是一样的，那么就可以利用一乘一除的方法来进行求解了，

#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

const ll INF = 1ll<<61;

using namespace std;

/ector

> G;

/pedef pair P;

/ector

> ::iterator iter;

//mapmp;

//map::iterator p;

int main

{

int p,q,r,s;

while(scanf(“%d %d %d %d”,&p,&q,&r,&s)==4)

{

int max1=max(p-q,q);

int max2=max(r-s,s);

int maxn=max(max1,max2);

double ans=1.00000;

for(int i=1;i<=maxn;i++)

{

if(i<=max1)

ans=ans/i*(p-max1+i);

if(i<=max2)

ans=ans/(r-max2+i)*i;

}

printf(“%.5lf\\n”,ans);

}

return EXIT_SUCCESS;

}<,int><,int>

篇2：《组合及组合数公式》的教学反思

《组合及组合数公式》的教学反思

通过“同课异构”活动，一方面，能把不同教师处理同一课堂内容的不同方式展示出来，再经过与其他参与活动的教师的交流研讨，以达到优化教学设计，不断积累教学方法，共同学习提高的目的；另一方面，通过该活动，也可强化不同学校教师之间的相互交流，实现资源共享，促进教师专业水平的发展。在此次同课异构的讲课与听课、评课全过程中，我感到受益匪浅、感悟颇多，现将此次同课异构的感悟归纳如下。

一、课的设计理念不一样

我的设计理念是基于我校的导学案而设计的实际应用型的一节课，着重在学生对组合概念和组合数公式的应用上；而周老师的设计理念是理论型的，着重在教给学生一种数学思维，注重概念的形成，对学生的层次要求相对较高。

二、课型结构不一样

我采用的是小组合作探究的形式，在导学案的基础上我让学生在自主、合作、探究的基础上去获得知识。我个人的理解是自主即学生自己单个的主动学习、合作就是学生之间的相互学习和讲解、探究就是在对于较难的问题的讨论得出统一的'认识。鉴于此我在本课堂上以学生的自主、合作、探究性活动为主线，引导他们通过类比推理与归纳推理的思想方法学习获得组合与组合数的概念，并通过猜想及推导得到组合数的计算公式。于是安排了这样的教学流程：首先从学生感兴趣的实际问题出发，明确组合概念；然后通过探究组合与排列个数间的联系，推导组合数公式；最后是简单应用、巩固练习、小结及作业。在这一节课上，由于发挥了学生自主参与的热情，学生上课活跃，积极思考，能从本质上较好的理解了组合的定义，也较牢固的掌握了组合数的计算方法，为他们接下来学习简单的组合实际问题奠定了基础。而周老师则让学生跟着自己的思路一步一步的得出概念、公式，让学生的思维更加严密。

三、课后反思

1、导学案的形式、内容、作用还有待优化。我们现在的导学案还有一点停留在练习题上，对学生的学科思维的培养还体现得不够

2、对课改和新的教学模式的理论了解还不够。因为没有足够的了解就不敢放开手大胆的体会新的理念和教学模式对教学效果的影响。

3、虽能让学生活跃于课堂之中，但教师在课堂上的主导作用仍显过度，学生依循教师的问题去思考从而获得知识固然不错，但我更希望能引导学生自己去发现并提出问题，我想这对于自己还需要一个更长并且耐心的探索。

4、小组的激励机制不够完善，评价还有待优化。但我想激励和评价都不能过度，否则会让学生忙于评比而疏于学习。

5、在教学过程中没有及时回归课本，没有引导学生在课本关键点处做记号或引导学生阅读课本相关概念。离开课本依赖学案。在以后的教学中应多引导学生进行教学的回归。

篇3：组合数计算C(n,m)加取模情况

想法：以前做比赛的时候遇到很多需要计算组合数的情况，都是当时手敲的，写递归不是暴就是超时啥的，或者是因为要取模，然后还要求逆元，所以敲得不是慢就是老是出问题，所以现在搞出模板来以后用就快了，

一：线性求C(n,m)

解释：由HDU 4927这道题求的组合数，可以了解到组合数的一些递推快速求法，因为这道题就是卡组合数的时间的。如果我们要算C(10,4)，我们可以先算C(10,1)，再算C(10,2)，再算C(10,3)，再算C(10,4)。为什么我要这么求呢？

因为：C(10,1)=10/1,然后C(10,1)*9/2就等于C(10,2)了，即C(10,2)=10*9/(2*1)；然后C(10,2)*8/3就等于C(10,3)了，即C(10,3)=10*9*8/(3*2*1)；然后C(10,3)*7/4就等于C(10,4)了，即C(10,4)=10*9*8*7/(4*3*2*1)。刚开始我还担心分子除以分母的时候可能会不得整除呢，但是放心，已经证明过了，可以这样递推的计算，得到的每个组合肯定是对的，不会出现小数点的情况。

所以根据这个性质或者说规律，可以用代码线性的求出C(n,m)了：

ll combine1(ll n,ll m) //计算组合数C(n,m)

{

ll sum=1; //线性计算

for(ll i=1,j=n;i<=m;i++,j--)

sum=sum*j/i;

return sum;

}

二：递归求C(n,m)

由c(n,m)=c(n-1,m-1)+c(n-1,m)，我们可以轻易的用代码递归得出C(n,m)的值：

ll combine2(ll n,ll m) //计算组合数C(n,m)

{

if(n==m||!m) return 1;//递归计算

return combine2(n-1,m)+combine2(n-1,m-1);

}

两种比较：线性的求组合数是很快的，每次只从1求到m即可；但是递归就不行了，计算C(50,25)的时候已经严重超时并暴了，等了好久都得不出答案，所以以后和线性的代码吧！

三：用线性求C(n,m)%mod

void extend_gcd(ll a,ll b,ll &d,ll &x,ll &y)

{

if(!b) d=a,x=1,y=0;

else

{

extend_gcd(b,a%b,d,y,x);

y-=x*(a/b);

}

ll Mod(ll a,ll b,ll mod)//算出的逆元不对，明天检查一下才行

{

if(!b) return 1;

ll ans=Mod(a,b>>1,mod);

ans=ans*ans%mod;

if(b&1) ans=ans*a%mod;

return ans;

}

ll inv(ll a,ll mod)//计算a对mod的逆元

{

ll d,x,y;

extend_gcd(a,mod,d,x,y);

return d==1?(x+mod)%mod:-1;

//return Mod(a,mod-2,mod);

}

ll combine1(ll n,ll m,ll mod)//计算组合C(n,m)%mod

{

ll sum=1; //线性计算

for(ll i=1,j=n; i<=m; i++,j--)

sum=sum*j*inv(i,mod)%mod;

return sum;

}

篇4：POJ 2992Divisors(求组合数质因子的个数)

DivisorsTime Limit:1000MSMemory Limit:65536KB64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2992 Appoint description:

Description

Your task in this problem is to determine the number of divisors ofCnk. Just for fun -- or do you need any special reason for such a useful computation?

Input

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

Output

For each instance, output a line containing exactly one integer -- the number of distinct divisors ofCnk. For the input instances, this number does not exceed 263- 1.

Sample Input

5 16 310 4

Sample Output

2616

题意：求C(n,m)的质因子的个数，

思路：知道公式很好做，不知道公式TLE到死，恰好我就是呢个不知道公式的，sad。

定理：设正整数n的所有素因子分解n=p1^a1*p2^a2*p3^a3****Ps^as,那么T(n)=(a1+1)*(a2+1)*(a3+1)***(an+1);（求因子的个数的公式）

1.求出N以内素数

2.ei=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]为取整。即可以 int ei=0;while(N) ei+=(N/=pi);

3.套公式计算了，M=（e1+1）*（e2+1）*……*（en+1）

#include#include#include#include#include#include#include #include#include#include#includeusing namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int prime[1010]= {2,3,5};int k=3;LL cnt[450][450];void is_prime{ int i,j; int flag=0; int gad=2; for(i=7; i<=1010; i+=gad) { flag=0; gad=6-gad; for(j=0; prime[j]*prime[j]<=i; j++) {if(i%prime[j]==0) { flag=1; break;} } if(!flag) {prime[k++]=i; } }}void get(){ is_prime(); LL s,ret,i,j; for(i=2;i<=431;i++){ for(j=0;prime[j]<=i;j++){s=i;ret=0;while(s){ s=s/prime[j]; ret+=s;}cnt[i][prime[j]]=ret; } }}int main(){ get(); LL n,m,i; LL res,ans; while(~scanf(“%lld %lld”,&n,&m)){ ans=1; for(i=0;prime[i]<=n;i++){res=cnt[n][prime[i]]-cnt[m][prime[i]]-cnt[n-m][prime[i]];ans*=(res+1); } printf(“%lld\\n”,ans); } return 0;}

篇5：组合数Cmn被素数整除的又一种判别法

组合数Cmn被素数整除的又一种判别法

1 问题的提出判断组合数Cmn是否被某素数整除这一问题,看似比较简单,但当m,n及素数比较大时,问题就变得较复杂了.[1,2],文[3]给出了组合数Cmn被素数整除的一种判别法,本文将给出组合数Cmn被素数整除的'又一种判别法.

作者：吴跃生作者单位：华东交通大学基础科学学院,330013 刊名：数学通报 PKU英文刊名：BULLETIN DES SCIENCES MATHEMATICS 年，卷(期)：2008 47(8) 分类号：O1 关键词：

UVA10375 Choose and divide 组合数.doc

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档