组合问题
时间：1s 空间：256M
题目描述：
求从n个不同物品中选出m个的方案数
输入格式：
一行，两个数n,m
输出格式：
方案数的个数
样例输入1：
5 2
样例输出1：
10
约定：
0<=m<=n<=100
提示：
2 个赞
大佬们给个思路
2 个赞
题目叫啥
2 个赞
组合问题
1 个赞
#include <stdio.h>
int a[21],n,r;
void dfs(int pos,int num)
{
if (pos==r) // 已有r个数
{
for (int i=0;i<r;i++)
printf("%3d",a[i]);
printf("\n");
return;
}
if(r-pos>n-num+1) return ;
for(int i=num;i<=n;i++)
{
a[pos]=i;
dfs(pos+1,i+1);
}
}
int main()
{
scanf("%d%d",&n,&r);
dfs(0,1);
return 0;
}
改一下变成计数就好了
2 个赞
一看题面就知道是组合，你就直接求(n,k)就可以了，你直接用公式算就可以了
2 个赞
为什么要递归，直接求阶乘不就可以了吗，而且这道题的数据范围足够小
2 个赞
怎么用公式？
1 个赞
\dfrac{n!}{(n-k)!k!}
把前n-k部分消掉，变成了
\dfrac{\Pi^n _{i=k+1} i}{k!}
时间复杂度为 \Theta(k+(n-k))=\Theta(n)
由于组合公式的结果总是为整数，所以不必考虑精度损失情况
证明如下
当 x=1 时， ( ^1 _k) 为 1 ，瞪眼法可知，它是整数
假设当 x=n 时， (^x _1) 至 (^x _x) 全部为整数，
由帕斯卡法则可知
(^{x+1} _k) = (^x _k) + (^x _{k-1})
加数都是整数，和也就是整数，因此组合的值总为整数
负数直接带进去也可知得数是整数
2 个赞
公式天书，不过我会了
1 个赞
范围为 0<=m<=n<=100
考虑排列组合
但这里是
所以明显是 C {m \choose n}
所以我们
所以做法1我们可以用Python
做法2 C++考虑 100! 非常大，我们需要高精
2 个赞
好的，谢谢提醒！
1 个赞
但是由于
所以我们可以先判断 m 与 n-m 的大小，挑小的进行运算，节省时空复杂度
2 个赞
错了，第二个公式改为 \dfrac{\Pi^n_{i=n-k+1}i}{k!}
2 个赞
66
1 个赞