【基础练习】组合数

谁践踏了优雅 2022-08-05 16:23 186阅读 0赞

题目来自 codevs 1631 洛谷 1173

很简单的递推题目 由刘汝佳紫皮（今后简称“ruka”）衍伸想要做的这道题目 稍后我将ruka版代码发上来

本题代码如下：

#include<iostream>
    #include<cstdio>
    #define num 100003
    using namespace std;
    long long a[1001][1001];
    int main(){
    	int i,j,n,k;
    	scanf("%d%d",&n,&k);
    	for (int i=0;i<=n;i++){
    		a[i][0]=1;a[i][i]=1;
    	}
    	for (i=1;i<=n;i++){
    		for (j=1;j<=i-1;j++){
    			a[i][j]=(a[i-1][j]+a[i-1][j-1])%num;
    		}
    	}
    	printf("%lld",a[n][k]);
    	return 0;
    }

刚开始的时候出现了严重错误 程序根本无法运行 调试会弹出CPU管理器 吓煞小生

经天意、李晨指点方得知

long long a\[1001\]\[1001\];  
这个句子应放在main函数外面 否则会爆栈 虽然现在还不明白为什么 但是应该记住   
还有就是为了防止出现错误 常量是很重要的  define 变量名 变量值  
题外话 现在还不习惯用CSDN 代码片不知道怎么去掉

那么 下面是ruka版代码

#include<cstdio>
    using namespace std;
    
    long long c(int n,int m){
    	if (m<=n-m) m=n-m;
    	long long ans=1;
    	for (int i=m+1;i<=n;i++) ans*=i;
    	for (int i=1;i<=n-m;i++) ans/=i;
    	return ans;
    }
    int main(){
    	int n,m;
    	scanf("%d%d",&n,&m);
    	printf("%lld\n",c(n,m));
    	return 0;
    }

显然这个程序效率严重不足 在上述两个OJ上均只得了30分【很大程度上是因为数据差不多吧···

然而这个程序有一些数学思想 也告诉我们n中选m和n中选n-m结果是一样的

但似乎还有一种更好的组合数公式 时间复杂度O（1） 但我现在想不起来了

——郁孤台下清江水，中间多少行人泪

李晨妹妹终于找到了我的博客 欢迎妹妹来刷访问量 我这小角落平时也没人来吧