题目意思就是说,给你n种食材,食材供应无限,然后要你选择k种食材做成一个沙拉,两份沙拉不同,当且仅当k重量食材的种类或配比不同。

普通的隔板法不允许有空组出现,而且容易理解,但是这里用到了分组为空的情况,所以我们先来举个例子介绍下允许分组为空隔板法:


> 假设我们有10个小球,将其放入3个盒子,盒子可以为空,请问共有多少种放法?


利用隔板法,我们只能在10个小球中间的9个位置插入隔板来分组,但是这样明显没有空的分组,怎么办?不如我们人为地在每个盒子里面放一个小球,这样就能保证每个盒子都能分到球,这样就符合普通隔板法的原理了。分完后,我们再人为地在每个盒子中去掉原来放入的一个球就符合题意了。所以,我们需要在10+3-1个位置中选择两个地方插入隔板,将其分为三组,这样就有C(10+3-1, 3-1),即为C(12,2)=66种分法。


> 对于本题的n种材料,选择k种组成沙拉,共有几种分法。


我们可以看成,将k个球放入n个盒子,盒子允许为空(材料可以不选)的情况。意思是什么呢,就是种类选择材料,如果k个球都在第一个盒子里面,那就是说k种材料都是第一种材料。那么总共的可能情况也就是C(k+n-1, n-1)种


如果还是难以理解,不如我们来看看水果分篮问题:


> 假设有4种水果西瓜、苹果、桃子、菠萝若干,从中任取5个,共有多少种方法?


这个问题可以看成,将5个水果篮分成四组分别放入水果,共有多少种方法?分成4组需要3个隔板,所以我们增加4个水果篮,这样可以放置的隔板就是5+4-1,然后从中选择3个位置放置隔板,保证每个位置都分到水果,分好水果后我们分别从每组拿走一个水果篮。就是C(5+4-1, 4-1)种,共C(8, 3)=56种。


地址:http://acm.uestc.edu.cn/#/problem/show/1401


代码:

StatusAccepted
Memory988kB
Length1190
LangC++


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
#defineFK(no, x) cout<<"Debug:"<<no<<"---"<<x<<"---"<<endl
#define PAIR pair<int, int>
typedef long long LL;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100000005;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
LL C(LL c, LL r){
    LL ans1=1, ans2=1;
    for(int i=0;i<r;i++){
        ans1*=c--;
        ans2*=r-i;
        LL gcd=__gcd(ans1, ans2);
        ans1/=gcd;
        ans2/=gcd;
    }
    return ans1/ans2;
}
int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k)){
        printf("%lld\n", C(k+n-1, n-1));
    }
    return 0;
}