【OJ】隔板法例子：魔法师问题

傷城~ 2023-10-10 09:23 88阅读 0赞

## 1644: 魔法师 ##

### 题目描述 ###

XR是一个魔法师。他想用花朵装饰我们的ACM/ICPC实验室。他有n个盒子，每个盒子里有无数朵花（因为他是魔法师）。在同一个盒子里的花都完全相同。当然，不同的盒子里的花颜色不同。

现在，XR想要从其中的一些盒子里取花朵，取出的花朵总数恰好为s。

我们想要知道，有多少种不同的取花朵的方法？从同一盒子里取出相同数量的花朵，只能算一种。

### 输入 ###

每组样例包含两个整数n和s(1≤n≤30, 1≤s≤32).

### 输出 ###

输出花朵的选取方案数。

### 样例输入 ###

1 3
    2 2

样例输出

1
    3

### 问题分析 ###

这是问题应该用隔板法来解决，隔板法可以参考[百度百科][Link 1]，很不错的例子。  
从百度百科中也可以学到，最终的结果为 `C(s+n-1,n-1)` ，这里面的C计算就是数学中排列组合中的 从`n+s-1` 中取出 `n-1` 个进行组合，有多少种结果。  
所以接下来就是把公式转换成函数的问题了，需要注意的是为了保证阶乘不超出范围，我们使用 `边阶乘边除` 的方法。

比如 C(A,a) 即 从A个取出a个进行组合，求多少种结果。根据数学公式，可以得出结果为 `A!/(a!*(A-a)!)`, 化简后结果为

(a+1)*(a+2)*...*A / (A-a)! 
    或者
    (A-a+1)*(A-a+2)*...*A / a!

代码如下：

#include <stdio.h>
    
    /** * 计算C(s+n-1,n-1)，具体分析请阅读文章 */
    long myCalc(int n, int s)
    { 
        long double result = 1;
        for(int i=1,j=s+n-1;i<=n-1;i++,j--)
            result=((long double)j*result)/(long double)i;   
        return result;
    }
    
    // written by Smileyan
    int main()
    { 
        int n,s;
        while(scanf("%d%d",&n,&s)==2)
        { 
            printf("%lld\n",myCalc(n,s));
        }
        return 0;
    }

### 总结 ###

重点是理解什么是隔板法，特别要注意结合百度百科关于隔板法的例子。和这个题目要求非常类似。

> 参考文章：  
> https://blog.csdn.net/hnust\_V/article/details/51746145
> 
> https://baike.baidu.com/item/%E9%9A%94%E6%9D%BF%E6%B3%95/3902458?fr=aladdin

> Smileyan  
> 2019年9月24日 18:57

[Link 1]: https://baike.baidu.com/item/%E9%9A%94%E6%9D%BF%E6%B3%95/3902458?fr=aladdin