P2638 安全系统题解

题目

特斯拉公司的六位密码被轻松破解后，引发了人们对电动车的安全性能的怀疑。李华听闻后，自己设计了一套密码：

• 假设安全系统中有n个储存区，每个储存区最多能存储存2个种类不同的信号（可以不储存任何信号）。有0和1这两种信号，其中0有a个，1有b个，单独一个0或1算一个信号。现要将这些信号储存在储存区中，0和1可以不用全部储存，一个存储区可以存放任意多个0和任意多个1。一种不同的储存方案经过李华处理后就将是一串不同的密码。

现在给出n,a,b，求可能的不同储存方案的个数。

输入输出格式

输入格式

第一行：共3个整数，n,a,b。

输出格式

第一行：一个整数，表示方案个数。

输入输出样例

输入样例

2 1 1

输出样例

9

解析

首先，既然不需要全部放进盒子里，那就讨论每一类球数确定时的情况。我们记n个盒子，放i个黑球以及j个红球（全部放进去）的方案数为f(n,i,j),(0≤i≤a, 0≤j≤b).

那么题中所求的总方案数就可以表达为：

那么现在我们需要知道这个f(n,i,j) 怎么算。

这是放i个黑球，再放j个红球的方案数，这两步操作是独立的，也就是f(n,i,j)=g(n,i)⋅g(n,j),

其中g(n,k) 表示的是n个盒子中放入k个同类球的方案数。

那么我们就只需要知道如何将k个球分给n个盒子了。

隔板法

我们先退一步。k个球分给n个盒子。我们假设，题目要求变为每个盒子至少要分得一个球，如何解决呢？

k个球之间形成了k−1个间隙，我们将n−1个隔板插入间隙中，隔板就将球分为了k份，符合假设。这样从k−1个间隙中选出n−1个插入隔板，即方案数为

但是现在要解决的情况是盒子可以分不到球。这样我们通过一步化归，转换为上面的情况：添加n个球，使每个盒子至少有一个球。这样分完后只要将每个盒子多拿的一个球收回，便回到原情况了。于是得到方案数.

这么一来，整个方案数的表达式已经确定了：

#include<cstdio>
using namespace std;
int n,a,b;
const int maxn=50
unsigned long long ans=0;
unsigned long long comb[maxn+1][maxn+1];
void prepare(){
    for(int i=0;i<=maxn;i++){
        comb[i][0]=comb[i][i]=1;
        for(int j=1;j<i;j++){
            comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    prepare();
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            ans+=comb[n+i-1][n-1]*comb[n+j-1][n-1];
        }
    }
    printf("%llu\n",ans);
    return 0;
}