题解：P2270 [HNOI2002] 奶牛的运算

1.题目大意：

有一个初始算式：

S=A_1-A_2-A_3-\dots-A_n

可以在其中添加

K

对括号（合法配对），形成不同的算式方案。两个方案本质不同当且仅当存在某个数列

A_1,A_2,\dots,A_n

使得计算结果不同。给定

n

和

k

，求本质不同的算式方案数量。

2.解题思路：

初始有 $n$ 个数，中间有 $n-1$ 个减号。
添加括号时不能在第一个数前加左括号（因为这样不会改变运算顺序），每对括号需要占据两个不同的减号位置。
问题转化为：从 $n-1$ 个减号位置中选出 $2k$ 个位置作为括号端点
公式： $ans=\sum_{i=0}^{\min(k,\lfloor\frac{n-1}{2}\rfloor)}\binom{n-1}{2i}$

3.代码实现：

CPP

#include<bits/stdc++.h>
using namespace std;
//打印__int128大整数
void print(__int128 x){
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
//计算组合数C(n,m)
__int128 getC(int n,int m){
	if(m==0)return 1;
	if(n<m)return 0;
	__int128 ans=1;
	for(int i=1;i<=m;i++){
		ans*=(n-i+1);
		ans/=i;
	}
	return ans;
}
int main(){
	int n,k;
	cin>>n>>k;
	__int128 sum=0;
	//累加C(n-1,0)+C(n-1,2)+...+C(n-1,2k)
	for(int i=0;i<=2*k;i+=2){
		sum+=getC(n-1,i);
	}
	print(sum);
	return 0;
}

题解：P2270 [HNOI2002] 奶牛的运算

文章操作

1.题目大意：

2.解题思路：

3.代码实现：

相关推荐

评论

题解：P2270 [HNOI2002] 奶牛的运算