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

cqbz_ycr · 2025-08-01 20:50:50 · 题解

1.题目大意：

有一个初始算式：S=A_1-A_2-A_3-\dots-A_n 可以在其中添加 K 对括号（合法配对），形成不同的算式方案。 两个方案本质不同当且仅当存在某个数列 A_1,A_2,\dots,A_n 使得计算结果不同。 给定 n 和 k，求本质不同的算式方案数量。

2.解题思路：

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

   3.代码实现：

   #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;
   }