NOIP组合数选题

时间：2018-10-18 22:35:36 阅读：173 评论：0 收藏：0 [点我收藏+]

前言：

“所有的组合数问题都是好题”

————清华某高材生zhx

组合数问题在近几年的NOIP的考试中多次露面，感觉有必要好好学一学

组合数的常见公式：

C ( i , j ) =

C（i，j） = C（ i-1 ， j） + C ( i -1 , j -1 ) ;

题目：

计算系数

noip2011提高组day2第1题

输入输出样例

输入样例：

1 1 3 1 2

输出样例：

这个题用到了二项式定理，在高二数学选修课本中讲到。不过，对于这个题你不需要知道这个知识，你只需要知道以下几点：

规定（a+b）^k k为指数

1 、二项式的系数就与杨辉三角有关，即与组合数有关

2、 k为几，就代表是杨辉三角的第几行

3、我们将上述二项式展开后可发现：越往后的每一项，a的指数是在递减的，而b的指数是在增加的，例如：第一项a的指数是k,b的指数是0 ，最后一项a的指数是0，b的指数是k

4、拓展：根据展开式可发现，二项式的系数是对称的

思路讲解：

我们已知上述信息之后便可轻松解决本题啦

1、二项式的指数是k,根据上面的信息2可知，答案在杨辉三角的第k行

2、根据上述信息4可知，我们求的是杨辉三角的第k行的第m项或者是第n项（对称性）

3、此题与原始组合数不同的是：我们需要在系数上乘上 a 的最终的值，再乘上 b 最终的值

我们可以思考：如果我们将 a 与 x 等同的看作是一个未知数的话，那么如果 x最终变成x^n ， a也应该等同的成为 a ^ n

所以答案就是 a的n次方乘以 b的m次方乘以杨辉三角的第k行，第n项

即系数最终的答案就是 a^n * b^m * C 【k】【m】

4、对于求解 a^n 和 b^m 我们可以用快速幂，但是要注意我们在读入a,b之后一定要先取一次模 ，否则我们在快速幂第一次计算 a*a 的时候会炸掉

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int c[1009][1009];


int quick_power(int a,int b ,int p){
    int ans=1;
    while(b>0){
      if(b%2==1)ans=(ans*a)%p;
    a=(a*a)%p;
    b=b/2;    
    }
    return ans;
}


int main(){
    int a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;
    a=a%10007;
    b=b%10007;
    c[1][1]=1;
    for(int i=0;i<=k;i++){
            c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007;
        }
    }
    
     
    a=quick_power(a,n,10007);
    b=quick_power(b,m,10007);
   
   
    cout<<((a*b)%10007*c[k][n])%10007<<endl;

    return 0;
}

组合数问题

NOIP提高组2016

输入输出样例

输入样例#1：

1 2
3 3

输出样例#1：

输入样例#2：

2 5
4 5
6 7

输出样例#2：

0
7

技术分享图片

思路讲解

既然上面那题都做完了，这个题也就不难了

这个题是让你找在不超过它给你的 i 和 j 的范围之内求组合数答案是 k 的倍数的数

我们可以先预处理出2000*2000 以内的所有的组合数

但是如果即使这样预处理了，我们对于每一组测试数据都暴力的去计算一遍有多少对的话，我们可以发现 2000*2000* 10000 是明显过不掉这道题的

我们观察一下，我们的k值是一直不变的，所以我们可以对于当前的每一个C（ i ， j）我们都可以用前缀和求出他之前有多少个，如果当前这个数是k的倍数的话（即：C( i， j )%k==0）我们就把刚求出来的前缀和+1就是当前的答案

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int c[2020][2020];
 8 int a[2020][2020];
 9 int t,k;
10 void  C(){
11     for(int i=0;i<=2018;i++){
12             c[i][0]=1;
13         for(int j=1;j<=i;j++){
14             c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
15         }
16     }
17 }
18 
19 
20 
21 
22 int main(){
23     c[1][1]=1;
24     scanf("%d%d",&t,&k);
25     C();
26     for(int i=2;i<=2018;i++){
27         for(int j=1;j<=i;j++){
28             a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
29             if(c[i][j]==0)a[i][j]=a[i][j]+1;    
30         }
31         a[i][i+1]=a[i][i];
32     }
33     for(int i=1;i<=t;i++){
34         int n,m;
35         scanf("%d%d",&n,&m);
36             if(m>n)m=n;
37             printf("%d\n",a[n][m]);
38     }
39     return 0;
40 }

最后加一道最简单的组合数问题练练手吧

扑克牌

附上链接：https://www.luogu.org/problemnew/show/P1358#sub

End.

NOIP组合数选题

原文：https://www.cnblogs.com/xiaoK-778697828/p/9813055.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)