洛谷题单指南-数学基础问题-P2638 安全系统

原题链接：https://www.luogu.com.cn/problem/P2638

题意解读：把a个红球、b个黑球放入n个盒子，求所有的方法。

解题思路：

盒子中可以放也可以不放，可以放任意个，因此，题目可以转化为将i个红球(0<=i<=a)，j个黑球(0<=j<=b)放入n个盒子的方案数之和，

设f(n, i, j)表示将一个红球、j个黑球放入n个盒子的方案数，本题答案用代码片段表示为

for(int i = 0; i <= a; i++)
{
    for(int j = 0; j <= b; j++)
    {
        ans += f(n, i, j);
    }
}

问题就转换为如何计算f(n, i, j)，也就是把i个黑球、j个红球放入n个盒子有多少种方法

设g(n, x)表示把x个球放入n个盒子有多少种方法，盒子可以为空

则根据乘法原理有：f(n, i, j) = g(n, i) * g (n, j)

现在问题集中在如何计算g(n, x)，即把x个球放入n个盒子有多少种方法（盒子可以为空）？

问题进一步转换为：把x + n个球放入n个盒子有多少种方法（每个盒子至少有1个球）？

这就是经典的插板法：

x + n个球中间有x + n - 1个空隙，可以插n - 1块板，方案数为C(x + n - 1, n - 1)

如上，问题得解。

100分代码：

#include <bits/stdc++.h>
using namespace std;

int n, a, b;

unsigned long long c[55][55], ans;

int main()
{
    cin >> n >> a >> b;

    //初始化组合数
    for(int i = 0; i < 50; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(j == 0) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }

    for(int i = 0; i <= a; i++)
    {
        for(int j = 0; j <= b; j++)
        {
            ans += c[i + n - 1][n - 1] * c[j + n - 1][n - 1];
        }
    }
    cout << ans;

    return 0;
}

仍有一个测试点过不了，大概率是超出unsigned long long，需要上高精度来计算组合数以及方案数了，忽略之。