牛客挑战赛37——牛牛与组合数数学（小白视角）

分手后的思念是犯贱 2023-07-07 11:27 23阅读 0赞

# 牛牛与组合数学（等效） #

## 做题心得 ##

在牛客里我已经不是第一次遇到求组合数了，但是由于组合数Cnm是好久之前学的，遇到题目时就懵了…… 具体格式：Cnm=n!/((n-m)!\*m!)，希望能够通过本次解析题目加深对组合数的理解。

## 牛牛与组合数数学题目 ##

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
[牛客网题目链接][Link 1]

## 题目分析 ##

该题我认为唯一的难点就是p的取值范围太大，不可以单纯用变量来存储p的值。因为题目输出要求并不高，只要判断Cnm与p是否相等。我们可以采用输入类（string）p再用**字符串化整数、分步求余**的方式一步一步转换为能够被变量存储的数值a，再通过**分步求余**的方式将Cnm求出b，问题变成**判断a与b的数值是否相等**。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int mod=1e9+7;
    //将输入转换为类
    //再通过分步求余的方式得到大小合适的sum
    //sum=n!/(m!*(n-m)!)
    //sum*(n-m)!=n!=sum1 
    int main()
    { 
    	ll n, m, sum=0, sum1=1, i;
    	string p;
    	
    	cin>>n>>m>>p;
    
    	for(i=0; i<p.size(); i++) sum=(sum*10+p[i]-'0')%mod;
    	for(i=1; i<=m; i++) sum=(i*sum)%mod;
    	for(i=n-m+1; i<=n; i++) sum1=(i*sum1)%mod;
    
    	if(sum==sum1)
    	cout<<"Yes!\n";
    	else
    	cout<<"No!\n";
    	
    	return 0;
    }

## 总结 ##

本题很简单，关键就是思维要清晰：找出问题关键 (Cnm与p是否相等—转换—a与b是否相等）。  
我一开始做这道题时，只想到将Cnm求余然后将p直接求余，没有考虑到p的数值过大肯定无法存储在变量中，应该向用类(string)来存储，在采用字符串化整数、分步求余的方式求出p的余数。  
**学习算法，思维很重要** 共勉！  
如果对本题有其他看法的话，欢迎老铁给小郑留言。

### 如果觉得该文章对你有用的话，可以给我一个大大的赞喔！！ ###

#### 老铁的关注是鼓励我写博客的最大动力~ ####

![被代码吃了][2020022315020267.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223113246252.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[Link 1]: https://ac.nowcoder.com/acm/contest/4381/B
[2020022315020267.png]: https://img-blog.csdnimg.cn/2020022315020267.png