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).

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

ans=\sum_{i=0}^{a}\sum_{j=0}^{b}f\left ( n,i,j \right )

那么现在我们需要知道这个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个插入隔板,即方案数为C_{k-1}^{n-1}

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

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

ans=\sum_{i=0}^{a}\sum_{j=0}^{b}f\left ( n,i,j \right ) =\sum_{i=0}^{a}\sum_{j=0}^{b}g\left ( n,i \right )g\left ( n,j \right ) =\sum_{i=0}^{a}\sum_{j=0}^{b}C_{i+n-1}^{n-1}\cdot C_{j+n-1}^{n-1}

#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;
}
上一篇:Redis锁,乐观锁与悲观锁


下一篇:封装的charts使用 vue2