UVA11955 Binomial Theorem 题解
UVA11955 Binomial Theorem
题目描述
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3106
输入格式
输出格式
输入输出样例 #1
输入 #1
3 (a+b)^1 (alpha+omega)^2 (acm+icpc)^3输出 #1
Case 1: a+b Case 2: alpha^2+2*alpha*omega+omega^2 Case 3: acm^3+3*acm^2*icpc+3*acm*icpc^2+icpc^3Solution
题目描述
输入若干组形如( a + b ) k (a+b)^k(a+b)k的二项式，输出该二项式的展开式；
这里的a , b a,ba,b可以是长度不超过 100 个字符的字符串。
输出按照a aa的降幂排列。
分析
1. 组合数
一般地，要从k kk个元素中选择t tt个元素的方案数称为组合数，用C k t C_k^tCkt来表示，其计算公式为
C k t = k ! t ! × ( k − t ) ! C_k^t=\dfrac{k!}{t!\times(k-t)!}Ckt=t!×(k−t)!k!
由于 Python 自带高精度，因此定义好求阶乘函数并按照上述公式定义求组合数的公式即可直接计算。参考代码（Python 中需要用双斜杠表示整除）：
#求阶乘函数deffact(x):return1if(x==0orx==1)elsex*fact(x-1)#组合数函数defC(n,r):returnfact(n)//fact(r)//fact(n-r)2. 二项式定理
( a + b ) k (a+b)^k(a+b)k展开式包含k + 1 k+1k+1项，这些项的系数依次是C k 0 , C k 1 , … , C k k C_k^0,C_k^1,\ldots,C_k^kCk0,Ck1,…,Ckk，也即
( a + b ) k = C k 0 × a k b 0 + C k 1 × a k − 1 b 1 + C k 2 × a k − 2 b 2 + … + C k k × a 0 b k (a+b)^k=C_k^0\times a^kb^0+C_k^1\times a^{k-1}b^1+C_k^2\times a^{k-2}b^2+\ldots+C_k^k\times a^0b^k(a+b)k=Ck0×akb0+Ck1×ak−1b1+Ck2×ak−2b2+…+Ckk×a0bk
3. 连接每一项
上述二项展开式从结构上可以看作是若干个字符串由加号进行连接的结果。在 Python 中可以使用"+".join(列表)的方法用加号连接一个列表中的所有元素，由此我们可以考虑将二项式的所有展开项存放在一个列表中进行连接。
4. 输出
4.1 特别注意k = 1 k=1k=1
这里的输出首先需要特判k = 1 k=1k=1的情况，如果次数为1 11，直接用加号连接两个变量名输出即可：
#特判次数为1的情况, 末尾不能输出^1if(p==1):return"%s+%s"%(v1,v2)4.2 把每一项制成字符串
其他情况下，按照二项式定理确定每一项的次数和系数，使用%d和%s格式化数字和变量名组成相应的字符串存入列表即可。需要说明的是不能输出“1 11次幂” 或者系数1 11。同样，开头和结尾次数为0 00要连同变量名都不输出，参考代码：
forkinrange(p,-1,-1):if(k!=0andk!=p):result.append("%d*%s^%d*%s^%d"%(C(p,k),v1,k,v2,p-k))elif(k==0):result.append("%s^%d"%(v2,p))elif(k==p):result.append("%s^%d"%(v1,p))4.3 判断幂次为1 11
判断幂次/系数为1 11容易想到的办法是直接replace("^1","")，但是由于题目中k ≤ 50 k\le 50k≤50，这会导致幂次为11 ∼ 19 11\sim 1911∼19时，十位的1 11被错误移除，因此这个方法不可行。判断幂次为1 11的正确方法是判断这个^1后面是不是紧挨着乘号或者加号，这是这个问题的关键。参考代码：
return"+".join(result).replace("^1*","*").replace("^1+","+")4.4 处理输入的内容
输入的两个变量和次数全部出现在同一行，一种可行的处理方法是将左括号(移除，+和)^全部替换为空格，然后用split()将表达式拆分为一个长度为 3 的列表。例如输入(alpha+omega)^3，拆分后的结果为["alpha","omega","3"]，列表第一个元素是变量名，第二个元素是另一个变量名，第三个元素转化为整数即为次数，按照 4.1~4.3 的方法处理即可。
完整代码
笔者认为分析中 4.1~4.3 的部分宜封装为函数来完成，代码中对于这些函数的功能已经给出了相应的说明。
#求阶乘函数deffact(x):return1if(x==0orx==1)elsex*fact(x-1)#组合数函数defC(n,r):returnfact(n)//fact(r)//fact(n-r)#输出展开式的某一部分, v1,v2是前后两个变量名,k为系数,p为次数defoutput(v1,v2,p):result=list()#特判次数为1的情况, 末尾不能输出^1if(p==1):return"%s+%s"%(v1,v2)#次数不为1的话就构造字符串forkinrange(p,-1,-1):if(k!=0andk!=p):result.append("%d*%s^%d*%s^%d"%(C(p,k),v1,k,v2,p-k))elif(k==0):result.append("%s^%d"%(v2,p))elif(k==p):result.append("%s^%d"%(v1,p))#次数不为1的情况下,出现的^1全部都紧挨着加号或乘号,可以利用这一点将其移除return"+".join(result).replace("^1*","*").replace("^1+","+")n=int(input())foriinrange(1,n+1,1):expr=input()var=expr.replace(')^',' ').replace('+',' ').replace('(','').split()x=var[0]y=var[1]print("Case %d:"%i,output(x,y,int(var[2])))Extra
从效果上看，本题相当于 Mathematica 中 Expand 函数的简化版本。